#4363. Path

题目描述

给出一个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