Bickford Fuse

On a sunny day, Hedgehog was walking through his favorite clearing when he noticed something unusual that had never been there before. From a distance it looked like a ball of tangled ropes. Up close, after he untangled it and examined the material, Hedgehog concluded that it was a Bickford fuse.

Hedgehog saw that whoever made it must have been bored and had a lot of free time. The fuse was knotted, and it had a huge number of knots! After counting carefully, he found that there are $n$ knots and $m$ connections between them. Each connection joins two knots and burns at a uniform rate. When a knot is lit, all connections that contain it start to burn.

Hedgehog did not like the find, so he decided to destroy it. He had a match in his pocket that he had forgotten about. He can light one of the knots with it, and the whole structure starts to burn. Hedgehog is a busy hedgehog and wants the structure to burn as fast as possible. Help him determine which knot he should light.

The first line contains two integers $n$ and $m$ ($2 \le n \le 100$, $1 \le m \le \frac{n \cdot (n - 1)}{2}$), the number of knots and the number of ropes between them.

Each of the next $m$ lines contains three integers $a_i$, $b_i$, and $t_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le t_i \le 1000$), the numbers of the knots joined by the $i$-th rope and the number of seconds that rope takes to burn completely when lit from one of its ends.

Each pair of knots is joined by at most one rope. It is guaranteed that the whole fuse can burn if any one of its knots is lit.

Print a pair of numbers: the number of the knot to light, and the time it takes for the whole fuse to burn when lit at that knot.