You will be given a tree with n node numbered 1 to n with weighted edge.

You will be asked q queries.

For each query you have to find the largest edge in path from A to B.

Input

The first line contains two integers n and q( 1 <= n, q <= 105 ). Each of the next n-1 lines contains three integer ui, vi, wi, ( 1 <= ui , vi <= n and 1 <= wi <= 105 ), meaning there is an edge between ui and vi with weight wi.

Each of the next q lines contains two integer A, B ( 1 <= A, B <= n and A != B ) describing the query.