Problem
Điểm tham quan "Mê cung tri thức" được xây dựng tại Trường Máy tính Mùa hè (LCS). Mê cung bao gồm N phòng, được đánh số từ 1 đến N, một số phòng có cửa giữa các phòng. Khi một người đi qua một cánh cửa, chỉ số kiến thức của anh ta sẽ thay đổi theo một lượng nhất định được ấn định cho cánh cửa này. Lối vào mê cung nằm trong phòng 1, lối ra – trong phòng N. Mỗi học sinh đi qua mê cung đúng một lần và được vào nhóm học này hay nhóm khác tùy theo lượng kiến thức thu được (khi vào mê cung chỉ số này bằng 0). Nhiệm vụ của bạn là hiển thị kết quả tốt nhất.
Đầu vào:
Dòng đầu tiên chứa số nguyên N (1 <= N <= 2000) – số phòng và M (1 <= M <= 10000) – Số cửa. Mỗi dòng trong số M dòng tiếp theo chứa mô tả về cửa – số phòng mà nó dẫn đến và nó dẫn đến (bạn chỉ có thể đi qua cửa theo một hướng), cũng như một số nguyên được cộng vào lượng kiến thức khi đi qua cửa (số này không vượt quá 10000 theo modulo). Cửa có thể dẫn từ một phòng đến chính nó, có thể có nhiều cửa giữa hai phòng.
Đầu ra:
Hiển thị ":)" – nếu bạn có thể nhận được lượng kiến thức không giới hạn, ":(" – nếu không thể vượt qua mê cung và lượng kiến thức tối đa thu được nếu không.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
2 2
1 2 3
1 2 7
|
7 |