e-olymp
Competitions

ADA Classes - November 6

Бикфордов шнур

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 - 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.

Input

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

Следующие m строк содержать описания соединений между узлами - три целых числа ai, bi и ti (1ai, bin, aibi, 1ti1000) - номера узлов, которые соединяет i-ая веревка и за сколько секунд эта веревка полностью сгорит, будучи подожжённой с одного из концов.

Каждую пару узлов соединяет максимум одна веревка. Гарантируется, что весь шнур может сгореть, если поджечь любой его узел.

Output

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