As a great traveler, your favorite thing to do is hit the road and explore. Today, you have arrived in a new country consisting of cities and bidirectional roads. These roads are structured such that each city is connected to at most bidirectional roads. After spending some time in City , you sense a strange, eerie atmosphere and decide you need to go to City to leave the country.

Suddenly, you realize that these bidirectional roads are subject to a mysterious restriction: each road has a fluctuation value and an energy cost . Whenever you exit a road, your personal fluctuation value is updated to match that road's fluctuation value . While traveling, if your current fluctuation value is , you can only enter a road whose fluctuation value falls between and inclusive. The cost of traversing a road is equal to its energy value.

Given that you can choose any initial fluctuation value to start your journey, you want to find out if it is possible to travel from City to City . If it is possible, output the minimum total cost required; otherwise, output to indicate that City is unreachable.

The first line contains four integers: 
(), as described in the problem statement.

The following  lines each contain four integers:  
(), representing the two cities connected by the bidirectional road, its fluctuation value, and its energy cost, respectively. It is guaranteed that there is at most one road between the same pair of cities.

If City  is reachable from City , output an integer representing the minimum total cost. Otherwise, output .

5 9 5 10
5 3 7 9
5 2 10 6
2 4 3 1
4 5 10 1
2 3 8 1
2 1 7 4
1 3 4 1
3 4 6 3
4 1 7 6

5

For the sample case, a feasible optimal path is as follows: set the initial fluctuation value to , pass through edge , then pass through edge  (at which point the fluctuation value becomes ), and finally pass through edge . The total energy value consumed is .