In a distant future, the world has reduced down to very few cities, all hostile to each other. So much so, that each city built its own roads to other cities, if needed and these roads were one way roads.

No one dares to walk on someone else's and even though teleportation is possible, the dangers involved are too great for anyone to risk their lives.

With time, however, certain cities became allies and certain blocks were formed. Within each block, trade was possible between any two cities by road but teleportation was used to reduce the travelling time to zero.

Bilbo wants to reach a city 'D' (destination) and he's at city 'S' in the shortest time possible. However, Bilbo has a map that's a few years old and represents the travelling time between two cities before the blocks described above were formed.

Your job is to find what the actual minimum possible time to travel from a city S to a city D for Bilbo.

Input

The first line of input will consist of two integers n and q. n represents the number of cities in the old map and q is the number of queries.

The next few lines of the input consist of 3 integers, i, j, k, which represents a one way road from city i to city j with travelling time of k. The roads information ends with an input of -1 -1 -1.

The next q lines contain 2 integers s d. s represents the source city and d represents the destination city.

Output

For each query you have to output a single line containing an integer denoting the minimum time possible between the two cities.

If no path is possible between the two cities, output “Unreachable” (quotes only for clarity).

Constraints

2

0

1

1

0

Example

Input: 6 5 0 1 2 1 2 10 0 3 9 4 5 2 4 1 15 2 4 20 3 4 8 -1 -1 -1 0 1 0 5 3 4 0 3 4 5 Output: 2 4 8 9 2