Fişierul intrare/ieşire:	sate.in, sate.out	Sursă	preONI 2007 Runda Finala
Autor	Filip Cristian Buruiana	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sate

Intr-o tara pitoreasca, intr-un judet de munte, sunt N sate coliniare numerotate cu numere naturale de la 1 la N. Sunt exact M perechi de sate intre care distanta este cunoscuta ( exprimata in kilometri ). Pe baza acestor informatii, trebuie determinata distanta intre satele 1 si N, daca acest lucru este posibil.

Date de intrare

Pe prima linie a fisierului sate.in se afla N si M, unde N este numarul de sate si M este numarul de relatii de forma precizata mai sus. Pe fiecare din urmatoarele M linii se gaseste cate un triplet (i j D), cu semnificatia ca distanta intre satele i si j este de D kilometri.

Date de iesire

Fisierul de iesire sate.out contine o valoare indicand distanta determinata intre satele 1 si N sau -1, in cazul in care distanta nu este determinata in mod unic de relatiile date.

Restrictii

• 1 ≤ N ≤ 300
• 1 ≤ M ≤ 1024
• Relatiile date nu sunt contradictorii

Exemplu

table(example). |_. sate.in |_. sate.out |
|7 3
1 5 20
3 7 15
1 3 8
|23
|
|50 2
1 20 1000
10 50 2000
|-1
|
|11 7
1 7 10
4 6 4
5 7 4
6 8 5
2 10 15
4 11 13
5 8 8
|
18
|

Cum se trimit solutii?