Train Ride
Recently, you moved to the new city, Umbristan, to work in the government sector.
You haven't been able to get your driver's license since moving to the city.
Therefore, you have to take the subway.
The subway can be denoted by n stations numbered from 1 to n. You live at station 1 and your workplace is located at station n.
There are a series of lines in the city which consist of train tracks running between two different stations. Each line is denoted by a number.
The Umbristan subway system has a strange fare system.
When you buy a ticket you can pay any price between 1 to k.
Then after purchasing the ticket, you can only ride the lines between 1 and the price you paid for the ticket (inclusive). For example, if you bought a ticket of price 3, then you can ride lines 1, 2 and 3.
Having recently moved to the city and lacking funds, you want to save as much money as possible. Thus, you are interested in finding the minimum price you have to spend in order to make it to your workplace.
Input
n: the number of stations. You live at station 1 and your workplace is located at station n.
k: the number of lines.
connections: a list of triplets where the first 2 values denotes the 2 stations connected and the 3rd value is the line it belongs to.
Output
If a path does not exist between your workplace and home, output -1, otherwise output the minimum ticket price needed for you to travel to your workplace.
Examples
Example 1:
Input:
n = 5, k = 2, connections = [[1, 2, 1], [2, 3, 1], [3, 4, 1], [4, 5, 1], [2, 4, 2], [1, 5, 2]]
Output:
1
Explanation:
You only need connections on line 1 in order to go from station 1 to station n.
Therefore, you only need to buy a ticket with price 1.