As a software developer you are tasked with developing a software to keep track of a large network of roads between cities. All the roads between the two cities require a certain toll fee and they are bi-directional.

Help the residents of your city find the best minimum price to pay to travel to another city to see their friends. On top of that, each traveller is only granted a certain amount of toll credit. You also need to make sure that the lowest toll fee shouldn't exceed the given budget.

Input Format

• The first line of input contains an integer N representing the number of cities.
• The second input line contains an integer M representing the number of roads.
• The Next M lines of input contain elements where each element is a tuple of the form (U, V, W) representing a road from city U to city V with a toll fee W.
• The next line of input contains an integer start representing the starting city.
• The next line of input contains an integer end representing the destination city.
• The next line of input contains an integer budget representing the maximum toll fee the traveler can afford.

Output Format Print an integer representing the minimum toll fee to travel from the starting city to the destination city without exceeding the budget. If there is no path from the starting city to the destination city within the budget, return -1.

Constraints

• 1 ≤ M, N ≤ 10^8
• 0 ≤ U,V ≤ N
• 1 ≤ W ≤ 10^8
• 0 ≤ start, end ≤ N
• 1 ≤ budget ≤ 10^3