题目描述

共有 $N$ 头奶牛（$2 \le N \le 1000$），编号为 $1 \sim N$，它们分别在编号同样为 $1 \sim N$ 的牧场上吃草，其中第 $i$ 头奶牛位于第 $i$ 号牧场。

牧场之间由 $N-1$ 条双向步道连接。第 $i$ 条步道连接牧场 $A_i$ 和 $B_i$，长度为 $L_i$（$1 \le L_i \le 10000$）。

任意两个不同牧场之间有且仅有一条通行路径，因此整张图构成一棵无根树。

现在给出 $Q$ 组询问，每组询问给定两个牧场编号 $p_1,p_2$，请你求出这两个牧场之间路径的总长度。

输入格式

• 第一行：两个整数 $N,Q$，分别表示牧场数量与询问组数。
• 第 $2 \sim N$ 行：每行三个整数 $A_i,B_i,L_i$，描述一条步道连接的两个牧场以及步道长度。
• 第 $N+1 \sim N+Q$ 行：每行两个整数 $p_1,p_2$，代表一组询问，查询对应两个牧场间的路径长度。

输出格式

• 共 $Q$ 行，每行输出一个整数，依次表示每组询问的答案，即两点之间路径的总长度。

输入输出样例

4 2 
2 1 2 
4 3 2 
1 4 3 
1 2 
3 2

2 
7

说明/提示

样例解释

• 第一组询问：牧场 $1$ 与牧场 $2$ 直接相连，路径长度为 $2$。
• 第二组询问：行走路径为 $3 \to 4 \to 1 \to 2$，总长度为 $2+3+2=7$。

数据范围

• $2 \le N \le 1000$
• $1 \le L_i \le 10000$
• $1 < Q < 1000$

60 28
1 2 1820
2 3 357
2 4 9641
2 5 8939
1 6 4524
2 7 9972
4 8 1616
2 9 650
9 10 2777
5 11 5558
3 12 8369
12 13 5718
7 14 1326
7 15 595
11 16 9991
8 17 7539
1 18 4381
14 19 1845
17 20 5967
14 21 8371
2 22 7117
21 23 1315
9 24 714
21 25 1211
11 26 1172
4 27 9759
4 28 1081
1 29 287
14 30 3117
30 31 2721
23 32 2351
1 33 8835
2 34 5495
10 35 2913
8 36 9120
23 37 5135
24 38 2559
29 39 224
3 40 9470
25 41 4420
7 42 6898
32 43 6560
6 44 4820
11 45 2145
11 46 577
12 47 3631
28 48 2793
18 49 6913
40 50 2887
37 51 4905
46 52 3789
7 53 2857
50 54 1389
53 55 624
22 56 8049
34 57 8685
5 58 9705
35 59 3819
47 60 2258
25 31
24 21
14 16
31 16
54 46
10 48
27 23
11 37
18 59
54 44
21 40
1 15
6 33
6 49
51 54
2 5
30 53
25 52
18 48
24 51
36 9
3 9
49 50
42 55
42 53
29 9
34 52
40 27

15420
21033
35786
41624
29177
16942
40384
40616
16360
25267
29496
12387
13359
15818
45127
8939
7300
39743
19716
32388
21027
1007
25828
10379
9755
2757
24358
29227

10 137
1 2 9005
2 3 2464
3 4 276
3 5 6491
3 6 8585
2 7 2328
1 8 7196
2 9 9555
8 10 7424
10 5
5 1
5 5
1 7
2 7
9 7
9 8
8 6
5 2
6 3
8 1
3 1
6 8
3 6
9 10
10 1
1 1
6 8
5 3
3 10
2 8
4 5
3 2
2 3
6 6
8 1
6 8
5 5
9 3
6 4
6 7
7 7
7 10
4 5
4 2
9 6
8 1
5 7
5 3
1 4
5 9
3 8
1 4
5 9
10 9
3 5
2 3
1 10
1 8
6 5
8 7
2 5
7 7
4 5
10 5
3 1
6 9
7 6
2 10
8 8
10 7
8 10
7 9
6 10
5 3
9 2
5 5
2 4
7 1
7 2
8 5
8 9
8 3
9 9
5 4
1 9
7 9
4 5
6 10
1 8
5 7
7 9
5 6
9 3
4 9
5 6
7 4
9 1
4 10
3 4
1 9
10 5
8 9
2 5
8 10
8 7
2 7
4 1
3 4
5 2
1 8
6 6
6 3
9 10
2 4
9 4
9 6
1 4
8 5
10 6
3 9
10 1
5 7
10 4
2 5
10 5
8 10
1 3
5 1
2 3
2 8
1 1
3 9
3 9
7 5
8 2
7 1
10 7
8 2
10 9
9 8
7 1
7 7
10 10
8 3
6 2
9 5

32580
17960
0
11333
2328
11883
25756
27250
8955
8585
7196
11469
27250
8585
33180
14620
0
27250
6491
26089
16201
6767
2464
2464
0
7196
27250
0
12019
8861
13377
0
25953
6767
2740
20604
7196
11283
6491
11745
18510
18665
11745
18510
33180
6491
2464
14620
7196
15076
18529
8955
0
6767
32580
11469
20604
13377
23625
0
25953
7424
11883
34674
6491
9555
0
2740
11333
2328
25156
25756
18665
0
6767
18560
11883
6767
34674
7196
11283
11883
15076
12019
12295
15076
5068
18560
26365
276
18560
32580
25756
8955
7424
18529
2328
11745
276
8955
7196
0
8585
33180
2740
12295
20604
11745
25156
34674
12019
14620
11283
26365
8955
32580
7424
11469
17960
2464
16201
0
12019
12019
11283
16201
11333
25953
16201
33180
25756
11333
0
0
18665
11049
18510