The delegation of high-school students arrived from the N-Region to the All-Russian Olympiad. Actually, to be more accurate to say "schoolgirls", because it consists of n talented girls. Of course, the organizers were not ready for such a situation and the resettlement was unexpected: every schoolgirl was settled in a separate single hotel room.

The next day in the same hotel several delegations were settled, one of which includes a student Slava. He could not pass by such an unusual delegation and decided late in the evening before the tour to get acquainted with at least one girl from the delegation of N-Region. Slava knows that at this time they are preparing for the competition, reading books, and are not arranged to receive visitors. So he decided to proceed as follows. The first thing he did was turning off the fuse near one of the rooms, so that the light in this room turns off. Left in the dark, the little girl will be scared, and will go to one of her friends (to the closest one) to continue preparing for the contest. And on this way she will be the most defenseless ...

Slava wants to know how much time he will have for acquaintance, and which girl he must to choose for it.

Input

First line contains numbers n and k (1 ≤ n, k ≤ 105) - the number of girls in delegation, and number of pairs of girls who are friends. Each of the next k lines contains three numbers ai, bi and wi - the numbers of girls who are friends and the distance between their rooms (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 105). It is guaranteed that no two girlfriends meet at input twice. It is guaranteed that every girl has a girlfriend.

Output

In the first line print one integer - the maximum time for acquaintance that Slava can provide for himself. In the second line print the number of schoolgirl that will be selected. If there are several schoolgirls, that provide maximum time for dating, output any of them.