* $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

| 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") ==

4851