BỘ BA CAO THỦ

Đất nước Halyp nổi tiếng với những câu chuyện thần thoại và bây giờ Halyp đang cần những vị thần xuất hiện để cứu đất nước thoát khỏi khủng hoảng.

Sau khi gia nhập thị trường chung nền kinh tế của Halyp không thể cạnh tranh được với các quốc gia khác trong khu vực, hậu quả là Halyp ngày càng suy sụp, nợ công ngày càng tăng và không có khả năng chi trả, hàng triệu người mất việc làm, người dân có tiền trong ngân hàng không thể rút được vì chính phủ liên tục thực hiện chính sách “Thắt lưng buộc bụng” để đáp ứng yêu cầu của chủ nợ. Trong bối cảnh đó người dân đang mơ về câu chuyện thần thoại về những chàng trai thông minh khỏe mạnh có thể giúp đất nước thoát khỏi thời kỳ tối tăm này. Theo nguyện vọng của người dân, chính quyền Halyp đã triệu tập được N chàng trai, được đánh số từ 1 đến N, để tổ chức M cuộc thi đấu. Theo thần thoại thì 2 người thi đấu với nhau phải là bạn bè từ trước, sức mạnh của 2 người A và B trong mỗi cuộc chiến được xách định bởi một số nguyên dương Strong(A,B). Cuối cùng họ chỉ chọn ra 3 người A, B, C sao cho Strong(A,B)+Strong(B,C)+Strong(A,C) lớn nhất.

Dữ liệu vào: từ tệp văn bản CAOTHU.INP

+ Dòng đầu tiên chứa 2 số nguyên dương N và M

+ M dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương lần lượt là u, v, Strong(u,v) cho biết u, v là bạn bè và trong cuộc chiến giữa u với v có chỉ số sức mạnh là Strong(u,v).

Dữ liệu ra: ghi vào tệp văn bản CAOTHU.OUT

+ Một số nguyên duy nhất là giá trị Strong(A,B)+Strong(B,C)+Strong(A+C) lớn nhất tìm được.

Ví dụ:

CAOTHU.INP	CAOTHU.OUT
5 7 1 2 5 1 3 4 2 3 10 2 5 3 3 4 6 3 5 4 4 5 1	19

* Giới hạn:

+ 30% số test có N<=100;

+ 70% số test có 100<N<=50000; 3<=M<=100000;

+ Giá trị Strong(A,B) nằm trong +phạm vi Longint

+ Thời gian cho mỗi test không quá 1 giây.

Dữ liệu vào luôn có lời giải!

SOLUTION - TEST - CODE