2250: 小机房的树
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：60
Solved：24
Description
小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去见面，但是作为两只虫子，他们不想花费太多能量。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以节省能量、尽快见面，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少能量
Input
第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的能量。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
Output
一共有m行，每一行一个整数，表示对于该次询问所得出的最少能量花费。
Sample Input Copy
3
1 0 1
2 0 1
3
1 0
2 0
1 2Sample Output Copy
1
1
2HINT
30%数据：1<=n<=1000， 1<=m<=1000， 0<=c<=1000
50%数据：1<=n<=10000， 1<=m<=10000， 0<=c<=1000
100%数据：1<=n<=50000， 1<=m<=75000， 0<=c<=1000