Problem
Atraksiyon "Bilgi Labirenti" Yaz Bilgisayar Okulu'nda (LCS) inşa edildi. Labirent, 1'den N'ye kadar numaralandırılmış, bazılarının aralarında kapı bulunan N odadan oluşur. Kişi bir kapıdan geçtiğinde, bilgisinin göstergesi bu kapı için belirlenmiş bir miktar değişir. Labirente giriş 1 numaralı odada, çıkış -dash; N odasında. Her öğrenci labirentten tam olarak bir kez geçer ve kazanılan bilgi miktarına bağlı olarak belirli bir çalışma grubuna girer (labirente girerken bu gösterge sıfırdır). Senin görevin en iyi sonucu göstermek.
Giriş:
Girişin ilk satırı N tamsayılarını içerir (1 <= N <= 2000) – oda sayısı ve M (1 <= M <= 10000) – Kapı sayısı. Sonraki M satırlarının her biri, kapının bir tanımını içerir – yönlendirdiği ve yönlendirdiği odaların numaraları (kapıdan yalnızca bir yönde yürüyebilirsiniz) ve ayrıca kapıdan geçerken bilgi miktarına eklenen bir tamsayı (bu sayı modulo'da 10000'i aşar). Kapılar bir odadan kendisine açılabilir, iki oda arasında birden fazla kapı olabilir.
Çıktı:
":)" göster – sınırsız miktarda bilgi edinebilirseniz, ":(" – labirent geçilemezse ve aksi takdirde kazanılan maksimum bilgi miktarı.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
2 2
1 2 3
1 2 7
|
7 |