Path

时间限制:10s      空间限制:256MB

题目描述

给出一个n个节点的无根树,边有权值。现在有m个询问,每个询问给出两个数k,x,你需要选择恰
好k条简单路径,满足:
•至少有一条路径经过编号为x的点
•这k条路径所包含的边的权值和尽可能大(每条边的权值只算一次)
你的任务即对每个询问给出可能的最大边权和。


输入格式

第一行二个整数n,m。
接下来n1行,每行三个整数x,y,v,描述一条边权为v的,连接x和y的边。保证v值之和不会
超过int。
接下来m行,每行二个整数k,x,描述一组询问。


输出格式

对于每组询问,输出一行一个整数,描述答案。


样例输入

6 3
1 2 2
2 3 2
3 4 2
4 6 1
3 5 10
3 1
4 1
2 2

样例输出

14
13
17

提示

1<=N,M<=10^5


题目来源

没有写明来源