一棵树有 个节点与 条边，其中第 条边连接节点 与 ，权值为 。
您需要处理 次询问。第 次询问可以记为三个整数 ， 和 。本次询问首先临时将第 条边的权值改为 。之后您需要选择 个不同的节点 并考虑树上的 条简单路径，其中第 条路径从节点 出发，到节点 结束。称一条边是好的，若它被所有 条路径包含。最大化好边的总权值。
请再次注意，所有询问对权值的修改都是临时的。在每次询问后，您需要把权值恢复原状。
每个测试文件仅有一组测试数据。
第一行输入两个整数 和 （，）表示节点的数量和询问的数量。
对于接下来的 行，第 行输入三个整数 ， 和 （，）表示第 条边连接节点 和 ，权值为 。
对于接下来的 行，第 行输入三个整数 ， 和 （，，）表示第 次询问。
每次询问输出一行一个整数表示答案。
7 3 1 2 20 2 3 10 2 4 40 4 6 10 1 5 30 5 7 10 2 100 1 5 50 2 2 100 3
160 110 20
对于第一次询问，选择 和 。
对于第二次询问，选择 ，， 和 。
对于第三次询问，选择 ，，，， 和 。
