Path Minimum

Problem Description

Given a tree with $n$ vertices, each edge has an edge weight. You are given $q$ queries $u, v$; for each query, report the minimum edge weight on the path between $u$ and $v$.

Input Format

The first line contains two integers $n, q\ (1 \le n, q \le 2 \times 10^5)$.

The next $n-1$ lines each contain two integers $u, v, w\ (1 \le w \le 10^9)$, denoting an edge and its weight.

The next $q$ lines each contain two integers $u, v\ (u \ne v,\ 1 \le u, v \le n)$, the two endpoints of a query.

Output Format

For each query, output one number: the answer.

Sample Input

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

Sample Output

2
3
5
2
3