Train Ride

Recently you've moved to the new city Umbristan working 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. There are a series of lines in the city which consist of train tracks running between 2 different stations. The lines are denoted by a number from 1 to k where 1 <= k <= n. 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 lines between 1 and the price you paid for the ticket(inclusive). You having recently moved to the city lack funds and wanting to save as much money as possible, you are interested in the minimum price you have to spend in order to make it to your workplace.

You live at station 1 and your workplace is located at station n.

The first input is the number n denoting the number of stations.

The second input is the number k denoting the number of lines.

The third input is a list of triplets where the first 2 values denotes the 2 stations connected and the 3rd value is the line it belongs to.

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.


Example 1:


n = 5, k = 2, connections = [[1, 2, 1], [2, 3, 1], [3, 4, 1], [4, 5, 1], [2, 4, 2], [1, 5, 2]]




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.




Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]

Get premium for instant access to all content and solutions