Revizia anterioară Revizia următoare
| 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. Se cunosc exact M perechi de sate intre care distanta este cunoscuta si este 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 ≤ 50
- 1 ≤ M ≤ 1024
- Relatiile date nu sunt contradictorii
Exemplu
| sate.in | sate.out |
|---|---|
| 7 3 1 5 20 3 7 15 1 3 8 | 23 |
