Heaviest Edge Query in Tree

You are given a tree with n nodes and n-1 weighted edges. The tree is undirected and connected. Each edge is described by a tuple (u, v, w) where w is the weight of the edge connecting nodes u and v.

You will be given q queries. Each query consists of two nodes u and v. Your task is to compute the weight of the heaviest edge on the unique simple path from u to v in the tree.

If u = v, then the answer is 0 because there is no edge along the path. Formally, if the unique path from u to v is represented as a sequence of edges with weights \(w_1, w_2, \ldots, w_k\), you are required to output \(\max\{w_1, w_2, \ldots, w_k\}\). If the path is empty, output 0.

inputFormat

The first line contains two integers n and q denoting the number of nodes in the tree and the number of queries respectively.

The next n-1 lines each contain three integers u, v, and w representing an edge between nodes u and v with weight w.

The following q lines each contain two integers u and v representing a query asking for the heaviest edge on the path between u and v.

outputFormat

For each query, output a single line with one integer: the weight of the heaviest edge on the path from u to v.

## sample

5 3
1 2 4
1 3 2
3 4 3
3 5 1
2 4
1 5
4 5

4
2
3

</p>