favorite We need a little bit of your help to keep things running, click on this banner to learn more

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. It is something from a 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 it was a huge amount of tied knots! After painstaking conversion, it was found out that there are a total n and units m connections between nodes. Each one connects two nodes and burns evenly. When node ignited light all the connections that contain it.

However, finding the Hedgehog did not like, and he decided to destroy it. To do this, he decided to use as the way a stray in his pocket the match. It can ignite it one of the nodes, and the whole structure begins to burn. Hedgehog - Sport Smeshariki, and wants this structure burned as quickly as possible. Help him to determine which node to do this, burn.


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 the 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 a 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 Анна Малова, Андрей Комаров