小嵐是今年的大一新人,但是因爲成大實在太大了,每次上課小嵐都會找不到教室,而且即使找到了,也會因為不知道最短路徑所以走很久(小嵐的腳踏車在大年初一那個大雪紛飛的夜晚被偷走了TT),因此小嵐希望繪製出一張成大地圖並且找出給定建築之間的最短路徑長,需要注意的是任兩建築均可以互相連通,且路徑唯一。
第一行有兩個整數 $N, M$,代表有 $N$ 棟建築和 $M$ 筆查詢。
接下來 $N-1$ 行每行有三個整數 $u, v, w$ 代表編號為 $u$ 和 $v$ 的建築間的路徑長度為 $w$,其為雙向邊。
最後 $M$ 行每行有兩個整數 $x, y$ 代表要查詢編號為 $x$ 和 $y$ 的建築之間的最短路徑長。
對於每筆查詢輸出最短路徑長。
No. | Testdata Range | Score |
---|---|---|
1 | 0~36 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 | |
31 | 1000 | 65536 | 65536 | |
32 | 1000 | 65536 | 65536 | |
33 | 1000 | 65536 | 65536 | |
34 | 1000 | 65536 | 65536 | |
35 | 1000 | 65536 | 65536 | |
36 | 1000 | 65536 | 65536 |