Description

给出N个点的一棵树，多次询问两个结点之间的最短距离。（边是双向边）

Input Format

测试数据第一行为两个数据N和M。N表示点数，M表示询问次数。接下来N-1行，每行3个整数x,y,k,表示点x到点y之间存在一条边长度为K。再接下来M行，每行两个整数x,y,表示询问点x到点y的最短距离。

Output Format

输出M行。对于每次询问，输出一行询问结果。

Sample

输入1：

2 2 
1 2 100
1 2
2 1

输出1：

100
100

输入2：

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

输出2：

10
25

Hint

1=<N<=100000,1=<M<=20000,1=<K<=100.