背景及描述

    有一只由n个结点组成的无根树，树边有权值，权值可正可负。有q组询问，每组询问两个点a和b，记dist[x,y]表示x结点和y结点在树上的路径经过的边的权值和，则需输出dist[k,a]+dist[k,b]的最小值，其中k为任意结点。

输入格式

    输入有n+q行，第一行有两个用空格隔开的正整数n、q。接下来的n-1行，每一行有三个用空格隔开的整数x、y、z，表示x结点和y结点之间有一条权值为z的边。接下来的q行，每一行有两个用空格隔开的正整数，表示每一组询问。

输出格式

    输出有q行，依次对应每组询问。

样例输入

5 3
1 2 3
1 3 -2
3 4 -1
3 5 -1
1 3
1 4
2 3

样例输出

-4
-5
-1

数据范围与约定

样例解释

    三组询问的最小值对应的k结点分别为4或5、5、4或5。

来源

经典试题改编