MARYBMW - BMW

no tags 

 

Mary is very very happy. You would be happy too if your parents give you the latest model BMW for your birthday. She wants to try out her new car and that's why she is going to visit her grandma.
There is a graph with N vertices representing N cities and M edges representing bidirectional roads between some pairs of cities. We can assume that Mary lives in city 1 and her grandma lives in city N. Unfortunately, not everything is so good in life and examples are the speed limits. Mary decided to drive with permanent speed. Each of these M roads has a maximum permissible speed V that Mary can't exceed. Well, her whims don't end here. As a lover of the extreme experiences she wants to drive her expensive car as fast as possible.
You are to write a program to find the maximum speed that Mary can reach her grandma's city without having arguments with the policemen(for their own good).

       Mary is very very happy. You would be happy too if your parents give you the latest model BMW for your birthday. She wants to try out her new car and that's why she is going to visit her grandma.

       There is a graph with N vertices representing N cities and M edges representing bidirectional roads between some pairs of cities. We can assume that Mary lives in city 1 and her grandma lives in city N. Unfortunately, not everything is so good in life and examples are the speed limits. Mary decided to drive with permanent speed. Each of these M roads has a maximum permissible speed V that Mary can't exceed. Well, her whims don't end here. As a lover of the extreme experiences she wants to drive her expensive car as fast as possible.

       You are to write a program to find the maximum speed that Mary can reach her grandma's city without having arguments with the policemen (for their own good).

       Note: There may be more than one road between two cities.

Input

       The first line of the input contains the number of tests – T (T <= 5). On the first line of each test case there are two integers – N (2 <= N <= 50000) and M (1 <= M <= 100000). On the next M lines there are three integers A, B, and V representing a bidirectional road between cities A and B with speed limit V where 1 <= V <= 10^18 (It's a BMW after all).

Output

       On a single line print the maximum possible speed Mary can reach. If she can't reach her grandma's house, print -1.

Example

Input:

1

4 5

1 2 80

3 1 20

2 3 60

4 3 300

2 4 90

Output:

80


hide comments
auler_: 2020-05-23 00:03:41

notice, n can be unreachable from 1.

amansahu112: 2020-04-16 14:50:42

100th AC .
hint:- kruskal then bfs

cenation007: 2019-08-20 14:20:30

fast input/output:)
AC

shubham97361: 2019-06-25 21:02:23

Just think little more about kruskal

a_98: 2019-05-23 15:54:02

My 100th AC :D :)

ayushgupta1997: 2019-02-24 08:45:03

use ios:: and "\n" to get AC if you are getting TLE!

smso: 2019-01-16 03:37:18

@febrin: thanks for the hint

Scale edge cost to [0.0,1.0] for use in Dijkstra's algorithm. Otherwise, 64bit integer overflow may occur for very large edge costs.

febrin: 2019-01-12 14:32:24

Time limit is fine and problem is interesting.
First find Maximal ST, then the minimal path in tree from 1 to n.
Remember about -1 if no such path exists

nadstratosfer: 2018-11-03 05:33:10

Another genius setting time limit as if there was danger of brute force solutions sneaking in. Downvoting.

ansh_gupta5076: 2018-01-11 14:48:58

use fast I/0 to overcome TLE


Added by:Extazy
Date:2015-12-28
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY