* $1 ≤ N ≤ 100$
* $1 ≤ K ≤ 5 000$

* $1 ≤ Q ≤ 2 500$

* Graful este conex (există cel puţin un drum între oricare două perechi de noduri).
* O muchie nu va apărea în fişierul de intrare de mai multe ori.
* Nu va exista în fişierul de intrare o muchie de la un nod la el însuşi.

h2. Exemplu
table(example). |_. drumuri3.in |_. drumuri3.out |

| 6 15 4 1 2

| 6 15 4 2

1 2
1 3
1 4

4 5
4 6
5 6

| 26 |

1 2
1 6
| 26
26
|

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

5300