Floyd - Warshall + Transitive closure

Detonating cord

In a beautiful sunny day Hedgehog was walking on his favorite meadow. However, he saw something unusual, that was not there before. From the distance it looked like a tangle of ropes. However, coming closer to untangle it and studied the material from which it is made, the Hedgehog came to the conclusion that this is a fuse.

Take a good look at him, the Hedgehog came to the conclusion, it seems that the one who made it, it was boring and he had a lot of free time, because the cord was tangled, and had a huge amount of knots! After careful reviewing, it was found out that there are a total n and units m connections between nodes. Each connection connects two nodes and burns evenly. When a node is ignited, all connections that contain it light up.

However, Hedgehog did not like the thing he found, and he decided to destroy it. To do this, he decided to use a match that was so conveniently lying in his pocket. He can set fire to one of the nodes, and the whole structure starts to burn. The hedgehog is a busy smesharik, and wants to burn this structure as fast as possible. Help him to determine which node must be set on fire for this.


The first line contains two integers n and m (2n100, 1mn · (n - 1) / 2) - the number of knots and ropes between the nodes, respectively.

Next m lines contain the description of connections between the nodes - three integers ai, bi and ti (1ai, bin, aibi, 1ti1000) - the numbers of nodes that the i - th rope connects and in how many seconds this rope will completely burn out, being set on fire from one of its ends.

Maximum one rope connects each pair of nodes. It is guaranteed that the entire cord can burn if any of its knots are set on fire.


Print the pair of numbers - the node number, which should be set on fire, and how long the whole cord will burn.


Time limit 1 second
Memory limit 128 MiB
Input example #1
4 4
1 2 3
2 3 4
1 3 5
1 4 1
Output example #1
2 4
Author Анна Малова, Андрей Комаров