== 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$
* **Atentie**: Pentru o intrebare $Xi$, $Yi$, $RMi$, doar obiectivele **intermediare** trebuie sa aibe riscul cel mult egal cu $RMi$
 
h2. Exemplu
 
table(example). |_. risc.in |_. risc.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="risc") ==