Tree Path Minimum Query

You are given a tree with N nodes where the nodes are numbered from 1 to N and the tree is rooted at node 1. Each edge in the tree has a positive integer weight. Your task is to answer Q queries. In each query, you are given two nodes u and v and you must determine the minimum edge weight on the path between these two nodes.

The problem can be formalized using the following notation:

Given a tree with N nodes and an edge set
\( E = \{ (u,v,w) \mid u \text{ is connected to } v \text{ with weight } w \} \), find for each query \( (u,v) \) the value \[ \min_{e \in \text{path}(u,v)} w(e), \] where \( w(e) \) is the weight of edge \( e \) on the unique simple path from u to v.

Note: It is guaranteed that the given edges form a valid tree.

inputFormat

The input is given via standard input (stdin) in the following format:

N Q
u1 v1 w1
u2 v2 w2
... (N-1 lines for the edges)
q1_u q1_v
q2_u q2_v
... (Q lines for the queries)

Where:

• N is the number of nodes in the tree.
• Q is the number of queries.
• Each of the next (N-1) lines contains three integers u, v, w representing an edge between nodes u and v with weight w.
• Each of the next Q lines contains two integers u and v representing a query.

outputFormat

For each query, print the minimum edge weight found on the path from u to v. Each answer should be printed on a new line to the standard output (stdout).

## sample

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

2
3
2

</p>