Am Valentinstag verteilt Farmer John Schokolade im Stall. $B$ Bullen ($1 \le B \le 25,000$) wollen sie einer besonderen Kuh schenken.

Jedes Tier weidet allein auf einer der $N$ Weiden ($2B \le N \le 50,000$), nummeriert $1..N$, mit $M$ Wegen in beide Richtungen ($N-1 \le M \le 100,000$) verschiedener Länge. Ein Paar kann mehrere haben. Weg $i$ verbindet $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), Länge $L_i$ ($1 \le L_i \le 2,000$).

Bulle $i$ ist auf $P_i$ ($1 \le P_i \le N$), schenkt der Kuh auf $Q_i$ ($1 \le Q_i \le N$).

Finde den kürzesten Weg zum Stall (1), dann zur Kuh. Der Stall erreicht alle über Wege und Weiden.

Beispiel mit 6 Weiden, 6 Wegen, 3 Bullen auf 2, 3, 5 für ihre Liebsten:

                      *1  <-- Bulle will Schokolade für Kuh auf Weide 1
             [4]--3--[5]  <-- [5] ist die Weidennummer
            /  |
           /   |
          4    2          <-- 2 ist die Weglänge
         /     |               zwischen [3] und [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• Der auf 2 geht 3 (zwei Wege) zum Stall, dann $2+1$ zu $[3]$, $[4]$ zum Schenken, insgesamt 6.

• Der auf 5 geht 3 nach 4, dann nach 3 und 1, insgesamt $3+2+1=6$.

• Der auf 3 geht 1 zum Stall 1 und 9 nach 6, insgesamt 10.

Eingabe

• Zeile 1: ganze Zahlen $N$, $M$, $B$, durch Leerzeichen getrennt.

• Zeilen $2..M+1$: Zeile $i+1$, Weg $i$ mit $R_i$, $S_i$, $L_i$, durch Leerzeichen getrennt.

• Zeilen $M+2..M+B+1$: Zeile $M+i+1$, $P_i$, $Q_i$, durch ein Leerzeichen getrennt.

Ausgabe

• Zeilen $1..B$: Zeile $i$, ganze Zahl, kürzester Weg von $P_i$ zum Stall für Schokolade und dann zur Traumkuh auf $Q_i$.

Beispiele

Eingabe 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

Ausgabe 1

6
6
10

Aufgabenautor: Brian Hamrick, 2010