Problem E: Travel with your girlfriend

Problem E: Travel with your girlfriend

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 81  Solved: 40
[Submit] [Status] [Web Board] [Creator:]

Description

作为一个防ac题,你点进来就是给我这个"简单题"面子,下面是送你一道良心的简单最短路径题

想在n个城市中(编号为0到n-1)选三个城市来旅游,又不想走过多的路,所以让你帮忙求下这个三个城市之间的最短路径是多少

Input

第一行输入 T表示T组数据然后输入一个n,代表n个城市,输入n-1行代表n-1条路,
每行 A B C 代表 城市A->城市B的距离是C ,输入Q 代表Q个查询每行输入 X Y Z
 求X,Y,Z这三个城市之间的最短路径是多少
 (1 < N < 50000) (1 < C < 100) (1 < Q < 70000)(T<20)

Output

每行输出一个数代表走的三个城市之间最短距离是多少

Sample Input Copy

2
4
0 1 1
0 2 1
0 3 1
2
1 2 3
0 1 2
5
0 1 1
0 2 1
1 3 1
1 4 1
2
0 1 2
1 0 3

Sample Output Copy

3
2
2
2