== 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$}. 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.
Intr-o tara pitoreasca, intr-un judet de munte, sunt $N$ sate coliniare numerotate cu numere naturale de la $1$ la {$N$}. Satele sunt asezate in ordine, de la stanga la dreapta, conform numerelor care le identifica. Astfel, satul $1$ este cel mai din stanga, in timp ce satul $N$ este cel mai din dreapta. Sunt exact $M$ perechi de sate intre care distanta este cunoscuta ( exprimata in kilometri ). Pe baza acestor informatii, trebuie determinata distanta intre satele $X$ si $Y$, 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 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.
Pe prima linie a fisierului $sate.in$ se afla {$N$}, {$M$}, {$X$} si {$Y$}, 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$ ({$i < j$}) este de $D$ kilometri.
h2. Date de iesire
Fisierul de iesire $sate.out$ contine, in ordine, raspunsurile date cartografilor care au pus intrebari, cate un raspuns pe linie.
Fisierul de iesire $sate.out$ contine o valoare indicand distanta determinata intre satele $X$ si $Y$.
h2. Restrictii
* $1 ≤ N ≤ 400$
* $1 ≤ M ≤ 2048$
* Relatiile descoperite de cartografi nu sunt contradictorii
* $1 ≤ N ≤ 30 000$
* $1 ≤ M ≤ 100 024$
* Pentru cel putin {$45%$} din teste, {$N ≤ 300$}
* Relatiile date nu sunt contradictorii
* Se garanteaza ca distanta intre satele $X$ si $Y$ este determinata in mod unic de relatiile date
* Distanta dintre oricare doua sate este un numar natural exprimat in kilometri
* Se garanteaza ca distanta intre satele $1$ si $N$ nu depaseste $20$ de milioane
* Intotdeauna va putea fi determinata distanta dintre $X$ si $Y$ pe baza informatiilor primite
h2. Exemplu
table(example). |_. sate.in |_. sate.out |
|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 11
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") ==
