K — Túrázás

Lea nagyon szereti a természetet, ezért gyakran jár túrázni a hétvégéken. Múlt vasárnap is korán kelt, egy hegy lábához hajtott, és épp ebédidőben ért fel a hegy tetejére. A desszert (almásrétes) közben jutott eszébe, hogy egy nagyon fontos találkozója lenne délután, amelyről lemarad, ha nem siet. Sietve ránézett a térképre, hogy megkeresse a leggyorsabb utat az autójához. Meglepetésére több száz ösvény vezetett lefelé, amelyek számos helyen keresztezték egymást, több ezer lehetséges útvonalat kínálva. Lea teljesen kétségbeesett. Szerencsére nála volt a műholdas telefonja, és felhívott… téged! Miután megadta neked az összes útvonalat, szeretné tudni, milyen messze is van most az autójától. Segíts neki!

A bemenet specifikációja

A bemenet első sora egy t egész számot tartalmaz (1 ≤ t ≤ 20). Ezt t teszteset követi. Két egymást követő teszteset leírását egy-egy üres sor választja el egymástól.

Minden teszteset két egész számmal, n-nel és m-mel kezdődik (1 ≤ n ≤ 1000, 1 ≤ m ≤ 50000), ahol n a kereszteződések száma, amelyeket 1-től n-ig sorszámozunk, m pedig az ösvények száma. Ezt m sor követi. Az i-edik sor három egész számot tartalmaz: v_i-t, w_i-t és c_i-t (1 ≤ v_i, w_i ≤ n, 1 ≤ c_i ≤ 1000). v_i és w_i az ösvények egy-egy kereszteződését, míg c_i a két kereszteződést összekötő szakasz hosszát adja meg. Az ösvények minden esetben kétirányúak. Lea jelenleg az 1-es számú, az autója pedig az n-nel jelölt kereszteződésnél áll.

A kimenet specifikációja

Minden tesztesetre egyetlen sort kell a kimenetre írni „Case #i: d” formában, ahol i a teszteset sorszáma (1-től indulva), d pedig az 1-es számú kereszteződéstől az n-nel jelölt kereszteződésig vezető legrövidebb útvonal hossza. A kimenet minden sorát újsor karakterrel kell lezárni.

1. példa bemenet

1. 4
2. 3 2
3. 1 2 1
4. 2 3 2
6. 3 3
7. 1 2 1
8. 1 3 3
9. 2 3 1
11. 3 2
12. 1 2 1
13. 2 3 2
15. 3 2
16. 1 3 5
17. 2 3 4

letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

1. Case #1: 3
2. Case #2: 2
3. Case #3: 3
4. Case #4: 5

letöltés szöveges állományként

2. példa bemenet

1. 7
2. 4 4
3. 1 3 2
4. 1 4 2
5. 2 4 5
6. 3 4 3
8. 5 4
9. 1 3 2
10. 1 4 1
11. 2 5 5
12. 3 2 4
14. 5 5
15. 1 3 2
16. 1 5 2
17. 2 4 5
18. 2 5 2
19. 4 5 2
21. 3 2
22. 1 2 1
23. 2 3 5
25. 2 1
26. 1 2 3
28. 4 4
29. 1 2 3
30. 2 4 4
31. 1 4 1
32. 3 4 2
34. 5 6
35. 1 2 2
36. 1 4 5
37. 3 4 2
38. 2 4 1
39. 2 3 1
40. 4 5 5

letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

1. Case #1: 2
2. Case #2: 11
3. Case #3: 2
4. Case #4: 6
5. Case #5: 3
6. Case #6: 1
7. Case #7: 8

letöltés szöveges állományként