ביום האהבה Farmer John מחלק שוקולד ברפת, ולכל אחד מ־$B$ הפרים ($1 \le B \le 25,000$) יש פרה מיוחדת שהוא רוצה להעניק לה מתנה.

כל פר ופרה רועה לבד באחד מ־$N$ שטחי המרעה ($2B \le N \le 50,000$), הממוספרים $1..N$ ומחוברים ב־$M$ שבילים דו־כיווניים ($N-1 \le M \le 100,000$) באורכים שונים. ייתכנו כמה שבילים ישירים בין זוג שטחים. שביל $i$ מחבר את $R_i$ ו־$S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), ואורכו $L_i$ ($1 \le L_i \le 2,000$).

פר $i$ נמצא ב־$P_i$ ($1 \le P_i \le N$) ורוצה להעניק לפרה ב־$Q_i$ ($1 \le Q_i \le N$).

מצאו את הדרך הקצרה ביותר מהמרעה הנוכחי לרפת (מרעה 1) ומשם למרעה של הפרה המיוחדת. אפשר להגיע מהרפת לכל שטח מרעה, אולי דרך שבילים ושטחים אחרים.

דוגמה עם 6 שטחים, 6 שבילים ו־3 פרים ב־2, 3, 5 המבקשים להעניק שוקולד לאהובותיהם:

                      *1  <-- הפר רוצה שוקולד לפרה במרעה 1
             [4]--3--[5]  <-- [5] הוא מספר המרעה
            /  |
           /   |
          4    2          <-- 2 הוא אורך השביל
         /     |               בין [3] ל־[4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• הפר ב־2 עובר מרחק 3 (בשתי דרכים) לרפת, ועוד $2+1$ אל $[3]$ ו־$[4]$ כדי להעניק, בסך הכול 6.

• הפר ב־5 הולך אל 4 במרחק 3, ואז ל־3 ול־1, בסך הכול $3+2+1=6$, כדי להעניק.

• הפר ב־3 הולך מרחק 1 לרפת 1 ואז נושא שוקולד עוד 9 עד 6, בסך הכול 10.

קלט

• שורה 1: המספרים השלמים $N$, $M$, $B$ מופרדים ברווחים.

• שורות $2..M+1$: שורה $i+1$ מתארת את שביל $i$ במספרים $R_i$, $S_i$, $L_i$ המופרדים ברווחים.

• שורות $M+2..M+B+1$: שורה $M+i+1$ מכילה $P_i$, $Q_i$ המופרדים ברווח.

פלט

• שורות $1..B$: שורה $i$ מכילה מספר שלם אחד, המרחק הקטן ביותר לפר ב־$P_i$ לקחת שוקולד מהרפת ואז לתת לפרת חלומותיו ב־$Q_i$.

דוגמאות

קלט 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

פלט 1

6
6
10

מחבר הבעיה: Brian Hamrick, 2010