== include(page="template/taskheader" task_id="sate") ==

Poveste si cerinta...

Intr-o tara pitoreasca, intr-un judet de munte, sunt $N$ sate coliniare numerotate cu numere naturale de la $1$ la {$N$}. Se stiu 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.

h2. 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.

h2. 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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50$
* $1 ≤ M ≤ 1024$
* Relatiile date nu sunt contradictorii

h2. Exemplu
table(example). |_. sate.in |_. sate.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|7 3
1 5 20
3 7 15
1 3 8
|23

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="sate") ==