题目内容

在一个由 $n$ 个枢纽和 $n-1$ 条管道构成的连通无环网络中，每条管道有一个正整数的长度。定义一条简单通路为序列中不重复经过任何枢纽的路径，其长度为经过的管道长度之和。

现在有 $m$ 次规划任务，每次给出两个枢纽 $x$ 和 $y$，你需要找到网络中必须包含这两个枢纽的简单通路中的最长长度。

数据范围：枢纽个数 $n$ 和询问次数 $m$ 均满足 $1 \le n, m \le 10^5$，管道长度 $w$ 满足 $1 \le w \le 10$。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示枢纽数量与询问次数。 接下来 $n-1$ 行，每行包含三个整数 $u, v, w$，表示枢纽 $u$ 与枢纽 $v$ 之间有一条长度为 $w$ 的管道。枢纽编号从 $1$ 到 $n$。