Detonating cord#2635
On a beautiful sunny day, the Hedgehog was walking through his favorite meadow. Suddenly, he saw something unusual that had never been there before. From a distance, it looked like a tangled ball of ropes. Getting closer, unravelling it, and examining its material, the Hedgehog realized it was a detonating cord.
Upon careful inspection, it seemed that whoever made it had a lot of free time, because the cord was tangled and tied with a huge number of knots! After meticulous counting, it was found that there are knots and connections between them. Each connection links two knots and burns uniformly. When a knot is ignited, all connections attached to it catch fire.
However, the Hedgehog did not like his discovery and decided to destroy it. For this, he used a match he conveniently had in his pocket. He can light any knot, after which the entire structure will start to burn. The Hedgehog is a busy smesharik and wants this structure to burn as quickly as possible. Help him determine which knot he should ignite.
The first line contains two integers and (2 \le n \le 100, 1 \le m \le n \cdot (n - 1) / 2) — the number of knots and the number of cords between them.
The next lines describe the connections between knots, each containing three integers a_i, b_i and t_i (1 \le a_i, b_i \le n, a_i \ne b_i, 1 \le t_i \le 1000) — the numbers of the knots connected by the -th cord and the number of seconds it takes to burn that cord completely starting from either end.
Each pair of knots is connected by at most one cord. It is guaranteed that the entire cord will burn if any of its knots are ignited.
Print two numbers: the number of the knot to be ignited and the time it takes for the entire cord to completely burn.
Example 1