Jan Ersa

Så här börjar en dikt av Gustaf Fröding:
Jan Ersa ägde Nackabyn,
Per Persa ägde Backabyn
i By i Västra Ed.
Jan Ersa,
Per Persa,
de höllo aldrig fred.

När Jan Ersa och Per Persa, på äldre dagar, flyttade in till staden såg de till att de hamnade så långt från varandra som möjligt. Skriv ett program som läser in information om gatorna i staden och som sedan bestämmer mellan vilka två hus den kortaste vägen är som längst, samt längden av denna väg.

Figure 1: Kartan visar stadens alla hus och gator i exemplet. Vi ser också de röda husen där Jan Ersa och Per Persa numera bor. Dessa två hus (nr 1 och 9) är de hus i staden som ligger längst ifrån varandra (4900 meter).

Input

På första raden står ett tal $N$, där $2 \le N \le 100$, som anger antalet hus i staden. Husen är numrerade från $1$ till $N$. På nästa rad återfinns ett tal som anger antalet gator $V$, där $2 \le V \le 500$. Därefter följer $V$ rader med tre tal på varje rad: från hus nummer, till hus nummer och gatans längd (givet i 100-tals meter). I givna indata går det alltid att ta sig från vilket hus som helst till vilket annat hus som helst.

Output

Programmet ska skriva ut en rad med tre tal åtskilda av blanksteg: Numren på de två husen längst ifrån varandra (det lägsta numret först) samt avståndet i meter. Om det finns flera par av städer som ligger på detta avstånd kan du ange vilket som helst av dem.

15
27
1 12 10
1 2 9
2 12 9
6 12 9
3 6 9
2 3 8
3 12 10
3 4 8
4 13 6
5 13 11
5 6 8
4 6 11
4 5 15
6 7 12
7 8 8
8 11 6
9 11 11
9 10 8
7 10 10
10 11 14
8 15 11
5 15 9
5 7 13
5 8 12
5 14 12
13 14 1
14 15 8

1 9 4900