Status

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

31.4% (11/35)

Description

小嵐是今年的大一新人，但是因爲成大實在太大了，每次上課小嵐都會找不到教室，而且即使找到了，也會因為不知道最短路徑所以走很久（小嵐的腳踏車在大年初一那個大雪紛飛的夜晚被偷走了TT），因此小嵐希望繪製出一張成大地圖並且找出給定建築之間的最短路徑長，需要注意的是任兩建築均可以互相連通，且路徑唯一。

Input Format

第一行有兩個整數 $N, M$，代表有 $N$ 棟建築和 $M$ 筆查詢。
接下來 $N-1$ 行每行有三個整數 $u, v, w$ 代表編號為 $u$ 和 $v$ 的建築間的路徑長度為 $w$，其為雙向邊。
最後 $M$ 行每行有兩個整數 $x, y$ 代表要查詢編號為 $x$ 和 $y$ 的建築之間的最短路徑長。

$1\leq N, M\leq 10^5$
$1\leq u, v, x, y\leq N$
$1\leq w\leq 10^9$

Output Format

對於每筆查詢輸出最短路徑長。

Sample Input 1

3 2
1 2 10
3 1 15
1 2
2 3

Sample Output 1

10
25

Sample Input 2

10 5
10 6 87
1 6 78
8 10 10
2 10 123
4 10 65
3 10 12
9 8 20
7 10 98
5 9 45
10 5
9 7
7 5
1 3
4 6

Sample Output 2

75
128
173
177
152

Hints

Problem Source

Subtasks

No.	Testdata Range	Score
1	0~36	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	65536	1
1	1000	65536	65536	1
2	1000	65536	65536	1
3	1000	65536	65536	1
4	1000	65536	65536	1
5	1000	65536	65536	1
6	1000	65536	65536	1
7	1000	65536	65536	1
8	1000	65536	65536	1
9	1000	65536	65536	1
10	1000	65536	65536	1
11	1000	65536	65536	1
12	1000	65536	65536	1
13	1000	65536	65536	1
14	1000	65536	65536	1
15	1000	65536	65536	1
16	1000	65536	65536	1
17	1000	65536	65536	1
18	1000	65536	65536	1
19	1000	65536	65536	1
20	1000	65536	65536	1
21	1000	65536	65536	1
22	1000	65536	65536	1
23	1000	65536	65536	1
24	1000	65536	65536	1
25	1000	65536	65536	1
26	1000	65536	65536	1
27	1000	65536	65536	1
28	1000	65536	65536	1
29	1000	65536	65536	1
30	1000	65536	65536	1
31	1000	65536	65536	1
32	1000	65536	65536	1
33	1000	65536	65536	1
34	1000	65536	65536	1
35	1000	65536	65536	1
36	1000	65536	65536	1

Submit