À la Saint-Valentin Farmer John distribue du chocolat à l’étable. $B$ taureaux ($1 \le B \le 25,000$) ont chacun une vache spéciale à qui l’offrir.

Chaque animal paît seul dans l’un des $N$ pâturages ($2B \le N \le 50,000$), numérotés $1..N$, reliés par $M$ chemins bidirectionnels ($N-1 \le M \le 100,000$) de longueurs variées. Plusieurs peuvent relier la même paire. Le chemin $i$ relie $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), longueur $L_i$ ($1 \le L_i \le 2,000$).

Le taureau $i$ est en $P_i$ ($1 \le P_i \le N$) et offre à la vache en $Q_i$ ($1 \le Q_i \le N$).

Trouvez le plus court trajet vers l’étable (1), puis la vache. L’étable rejoint tous les pâturages via chemins et pâturages.

Exemple de 6 pâturages, 6 chemins, 3 taureaux en 2, 3, 5 offrant à leurs aimées :

                      *1  <-- Taureau voulant du chocolat pour la vache du pâturage 1
             [4]--3--[5]  <-- [5] est le numéro du pâturage
            /  |
           /   |
          4    2          <-- 2 est la longueur du chemin
         /     |               entre [3] et [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• Celui de 2 parcourt 3 (deux trajets) vers l’étable puis $2+1$ vers $[3]$, $[4]$ pour offrir, total 6.

• Celui de 5 va en 4 pour 3 puis en 3 et 1, total $3+2+1=6$.

• Celui de 3 parcourt 1 vers l’étable 1 puis 9 vers 6, total 10.

Entrée

• Ligne 1 : entiers $N$, $M$, $B$ séparés par des espaces.

• Lignes $2..M+1$ : ligne $i+1$, chemin $i$ avec $R_i$, $S_i$, $L_i$ séparés par des espaces.

• Lignes $M+2..M+B+1$ : ligne $M+i+1$, $P_i$, $Q_i$ séparés par un espace.

Sortie

• Lignes $1..B$ : ligne $i$, entier, trajet minimal de $P_i$ à l’étable pour prendre le chocolat puis à sa bien-aimée en $Q_i$.

Exemples

Entrée 1

6 7 3
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
2 4
5 1
3 6

Sortie 1

6
6
10

Auteur du problème : Brian Hamrick, 2010