risc

Risc

== include(page="template/taskheader" task_id="risc") ==
Bianca este agent secret la agentia BBB. Ea are o harta cu $N$ obiective strategice, unite intre ele prin $M$ drumuri bidirectionale fiecare cu o anumita lungime $Li$. Pentru fiecare obiectiv Bianca stie gradul de risc $Ri$ al acelui obiectiv (cu cat e mai mare gradul de risc cu atat sunt mai mari sansele ca Bianca sa fie prinsa si incarcerata). Acum Bianca incearca sa execute planul urmatoarei misiuni. Ea isi pune $Q$ intrebari de genul: care este drumul minim intre obiectivele $Xi$ si $Yi$ astfel incat orice nod intermediar prin care trec are riscul cel mult $RMi$? Ajutati-o pe Bianca sa isi indeplineasca misiunea cu succes.

 
h2. Date de intrare
 
Fişierul de intrare $risc.in$ va contine pe prima linie trei numere naturale $N$, $M$ si $Q$, separate prin cate un spatiu, avand semnificatiile din enunt. Urmatoarea linie contine $N$ numere, al i-lea dintre acesta fiind $Ri$, riscul obiectului $i$. Urmatoarele $M$ linii contin fiecate cate trei numere $Xi$, $Yi$ si $Li$ reprezentand faptul ca intre obiectivele $Xi$ si $Yi$ exista un drum bidirectional de lungime $Li$. Urmatoarele $Q$ linii contin cate trei numere $Xi$, $Yi$ si $RMi$ reprezentand cate o intrebare a Biancai.
 
h2. Date de ieşire
 
În fişierul de ieşire $risc.out$ veti afisa $Q$ linii. Pe linia $i$ veti afisa raspunsul la a $i$-a intrebare a Biancai, reprezentand distanta minima intre obiectivele $Xi$ si $Yi$ astfel incat orice nod intermediar de pe drumul dintre aceste noduri sa nu aibe riscul mai mare decat $RMi$, sau $-1$ in caz ca nu exista un astfel de drum.
 
h2. Restricţii
 
* $1 ≤ N ≤ 300$
* $1 ≤ M ≤ N^2^$
* $1 ≤ Q ≤ 100 000$
* $1 ≤ Li ≤ 100 000$
* $1 ≤ Ri, RMi ≤ 100 000$
* Pentru $50%$ din teste $N ≤ 100$
* **Atentie**: Pentru o intrebare $Xi$, $Yi$, $RMi$, doar obiectivele **intermediare** trebuie sa aibe riscul cel mult egal cu $RMi$
* Doua obiective pot fi unite prin mai multe drumuri
* Drumul minim de la un obiectiv la el insusi are distanta $0$
 
h2. Exemplu
 
table(example). |_. risc.in |_. risc.out |
| 5 6 6
5 4 3 2 1
1 2 1
2 3 1
3 4 5
4 1 3
4 5 10
5 2 2
3 1 1
3 1 2
3 1 4
4 2 1
4 2 3
4 2 5
| -1
8
2
12
6
4
|
 
== include(page="template/taskfooter" task_id="risc") ==

4851