Falvak
Ismerjük egy megye települései közötti utak hosszát. Zsákfalunak nevezzük azt a falut, ahova csak egyetlen út vezet (és ahonnan már nem lehet tovább menni, csak visszafelé).
A településeket sorszámukkal azonosítjuk.
Feladat
Készítsünk programot, ami megadja...
A. a leghosszabb utat, amiről nem lehet letérni és zsákfaluhoz vezet;
B. azokat a településeket, ahova a legtöbb út vezet (ha több is van, akkor mindegyiket);
C. azt a települést, amitől a legközelebbi szomszédja legmesszebb van (ha több is van, akkor a legkisebb sorszámút).
Bemenet
A falvak.be szöveges állomány első sorában a települések ($2\le N\le 1000$) és az utak száma van ($1\le M\le 100000$), egy szóközzel elválasztva. A következő M sor mindegyikében három egész szám van, egy-egy szóközzel elválasztva: egy-egy út két végpontjának sorszáma, valamint a köztük lévő út hossza.
Kimenet
A falvak.ki szöveges állomány első sorába a zsákfalvakba vezető leghosszabb út hosszát; a második sorába a legtöbb utas települések sorszámát (ha több ilyen van, akkor sorszám szerint növekvő sorrendben és szóköz válassza el őket egymástól), a harmadikba pedig a település sorszámát kell írni!
Példa
| falvak.be | falvak.ki |
8 8
1 2 10
2 3 15
2 4 10
2 5 5
3 5 5
4 5 15
5 6 5
6 7 10
|
15
2 5
1
|
Tesztadatok
