Social Cow Gathering

There are \( N \) cows grazing in \( N \) pastures, where cow \( i \) is initially in pasture \( i \). The pastures are connected by \( N-1 \) bidirectional walkways that form a tree. Each walkway \( i \) connects pastures \( A_i \) and \( B_i \) with a length of \( L_i \). Since the walkways form a tree, there is exactly one unique path between any two pastures.

You are given \( Q \) queries. Each query provides two pasture numbers \( p_1 \) and \( p_2 \) and asks you to compute the total length of the unique path between them.

Constraints:

• \( 2 \leq N \leq 1000 \)
• \( 1 \leq L_i \leq 10,000 \)
• \( 1 \leq Q < 1000 \)

inputFormat

The first line contains two integers \( N \) and \( Q \) separated by a space.

The next \( N-1 \) lines each contain three integers \( A_i \), \( B_i \), and \( L_i \) separated by spaces, representing a bidirectional walkway between pastures \( A_i \) and \( B_i \) with length \( L_i \).

The following \( Q \) lines each contain two integers \( p_1 \) and \( p_2 \), representing a query for the path length between these two pastures.

outputFormat

For each query, output the total length of the unique path between the two specified pastures on a new line.

sample

2 1
1 2 3
1 2

3