Problem
Tarikan "Labyrinth of Knowledge" dibina di Summer Computer School (LCS). Labirin terdiri daripada N bilik, bernombor dari 1 hingga N, beberapa daripadanya mempunyai pintu di antaranya. Apabila seseorang melalui pintu, penunjuk pengetahuannya berubah dengan jumlah tertentu yang ditetapkan untuk pintu ini. Pintu masuk ke labirin adalah di dalam bilik 1, pintu keluar – di bilik N. Setiap pelajar melalui labirin tepat sekali dan masuk ke dalam satu atau kumpulan belajar yang lain bergantung pada jumlah pengetahuan yang diperoleh (apabila memasuki labirin, penunjuk ini adalah sifar). Tugas anda ialah untuk menunjukkan hasil yang terbaik.
Input:
Baris pertama input mengandungi integer N (1 <= N <= 2000) – bilangan bilik dan M (1 <= M <= 10000) – Bilangan pintu. Setiap baris M seterusnya mengandungi penerangan tentang pintu – bilangan bilik dari mana ia menuju dan ke mana ia menuju (anda hanya boleh berjalan melalui pintu dalam satu arah), serta integer yang ditambah kepada jumlah pengetahuan apabila melalui pintu (nombor ini tidak melebihi 10000 dalam modulo). Pintu boleh mengarah dari bilik ke pintu itu sendiri, boleh terdapat lebih daripada satu pintu antara dua bilik.
Output:
Paparan ":)" – jika anda boleh mendapatkan jumlah pengetahuan yang tidak terhad, ":(" – jika labirin tidak dapat dilalui, dan jumlah maksimum pengetahuan yang diperoleh sebaliknya.
Contoh
| # |
Input |
Output |
| 1 |
2 2
1 2 3
1 2 7
|
7 |