== include(page="template/taskheader" task_id="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.

Intr-o tara pitoreasca, intr-un judet de munte, sunt $N$ sate coliniare numerotate cu numere naturale de la $1$ la {$N$}. La ultima conferinta a cartografilor a fost pusa in discutie tocmai dispunerea acestor sate. La conferinta au participat exact $M$ cartografi. Fiecare cartograf, in ordine, de la $1$ la {$M$}, cand ia discursul, fie prezinta o noua descoperire, fie pune o intrebare despre dispunerea satelor. Astfel, cartograful cu numarul de ordine $k$ urmeaza dupa primii $k-1$ cartografi si poate:
 
* sa precizeze distanta dintre satele $i$ si {$j$} ({$i < j$}). Distanta este un numar natural si este exprimata in kilometri
* sa intrebe care este distanta intre satele $i$ si $j$ ({$i < j$}). Raspunsul ii va fi dat de un program care tine cont de toate descoperirile cartografilor care au luat cuvantul inaintea sa. Daca distanta nu poate fi determinata conform indiciilor existente pana in prezent, programul va returna valoarea {$-1$}.
 
Sa se determine raspunsul dat de program fiecarui cartograf care pune o intrebare.

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.

Pe prima linie a fisierului $sate.in$ se afla $N$ si {$M$}, unde $N$ este numarul de sate si $M$ este numarul de cartografi. Pe fiecare din urmatoarele $M$ linii se gaseste descrierea actiunii unui cartograf. Astfel, daca primul numar de pe linie este {$0$}, atunci cartograful curent a realizat o noua descoperire. Pe aceeasi linie urmeaza $3$ numere naturale {$i j D$}, indicand faptul ca distanta dintre satele $i$ si $j$ ({$i < j$}) este de $D$ kilometri. Daca primul numar de pe linie este {$1$}, atunci cartograful curent pune o intrebare. Urmeaza pe aceeasi linie doua numere $i$ si $j$ ({$i < j$}). Programul automat ii va raspunde cu distanta dintre satele $i$ si $j$ folosind toate informatiile existente pana in prezent sau cu {$-1$}, daca aceasta distanta nu poate fi determinata.

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.

Fisierul de iesire $sate.out$ contine, in ordine, raspunsurile date cartografilor care au pus intrebari, cate un raspuns pe linie.

h2. Restrictii

* $1 ≤ N ≤ 300$
* $1 ≤ M ≤ 1024$
* Relatiile date nu sunt contradictorii
* Distanta dintre oricare doua sate este un numar natural exprimat in kilometri

* $1 ≤ N ≤ 400$
* $1 ≤ M ≤ 2048$
* Relatiile descoperite de cartografi nu sunt contradictorii

* Se garanteaza ca distanta intre satele $1$ si $N$ nu depaseste $20$ de milioane

h2. Exemple

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

|10 5
0 3 7 9
0 5 9 9
0 5 7 5
1 3 5
1 7 8
0 8 9 1
1 7 8
|4
-1
3

|

|11 7
1 7 10
4 6 4
5 7 4
6 8 5
2 10 15
4 11 13
5 8 8
|18
|

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