#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
// Egy beolvasott el adatai
struct El {
// Kezdopont / csucs indexe (1-tol kezdve)
int honnan;
// Vegpont / csucs indexe (1-tol kezdve)
int hova;
// A ket vegpont tavolsaga
int tav;
};
// Beolvassa az elek listajat a 'be' bemenetrol egy vektorba.
std::vector<El> beolvas(std::istream &be) {
int n;
be >> n;
std::vector<El> elek(n - 1);
for (auto &el : elek) {
be >> el.honnan >> el.hova >> el.tav;
}
return elek;
}
// Egy csucs szomszedos csucsanak adatai
struct Szomszed {
// A konstruktorra azert van szukseg, hogy az std::vector
// 'emplace_back' tagfuggvenyet tudjuk hasznalni uj elem hozzafuzesere.
Szomszed(int p_csucs, uint64_t p_tav) :
csucs{ p_csucs },
tav{ p_tav } { }
// A szomszedos csucs indexe
int csucs;
// A szomszedos csucs tavolsaga
uint64_t tav;
};
// Egy csucs adatai
struct Csucs {
// Szulo csucs indexe (a gyoker elem eseten -1)
int szulo = -1;
// A csucsbol kiindulo leghosszabb ut kovetkezo csucsanak indexe
int max_szomszed = -1;
// A szulo csucstol valo tavolsag (a gyoker elem eseten -1)
uint64_t szulo_tav = 0;
// A csucsbol kiindulo leghosszabb ut hossza
uint64_t max_tav = 0;
// A csucsbol kiindulo masodik leghosszabb ut hossza
uint64_t max_tav_max_szomszed_nelkul = 0;
// A csucs szomszedos csucsai beleertve a szulo csucsot is
std::vector<Szomszed> szomszedok;
};
// A graf egy csucsokbol allo tomb
using Graf = std::vector<Csucs>;
// Az elso melysegi bejaras soran minden csucshoz kiszamitjuk az onnan kiindulo
// leghosszabb, lefele vezeto ut hosszat es a hozza tartozo kovetkezo csucs indexet,
// tovabba a masodik leghosszabb ut hosszat.
void dfs_1(int akt, Graf &g) {
auto &akt_csucs = g[akt];
for (const auto &szomszed : akt_csucs.szomszedok) {
// Az elso bejaras soran csak a lefele meno utakat vesszuk figyelembe, azaz
// a szomszedos csucso kozul ki kell hagyni a szulo csucsot.
if (szomszed.csucs != akt_csucs.szulo) {
// Mielott az egy szinttel lejjebb levo szomszedos csucsot feldolgoznank,
// beallitjuk a 'szulo' es 'szulo_tav' mezoit, azaz kialakitjuk
// a graf fa szerkezetet. A feldolgozas soran ezekbol tudjuk
// megallapitani, hogy mely csucsok vannak egy szinttel feljebb,
// illetve lejjebb.
g[szomszed.csucs].szulo = akt;
g[szomszed.csucs].szulo_tav = szomszed.tav;
// Feldolgozzuk az egy szinttel lejjebb levo szomszedos csucsot.
dfs_1(szomszed.csucs, g);
// Ezen a ponton mar ismerjuk az elobb feldolgozott szomszedos csucshoz tartozo
// maximalis, lefele meno ut hosszat (g[szomszed.csucs].max_tav).
// Az aktualis csucsbol (akt) kiindulo, aktualis szomszedon (szomszed.csucs)
// keresztul futo maximalis ut hossza tehat egyenlo a szomszedos
// csucshoz tartozo maximalis ut hosszaval plusz az aktualis es a szomszedos
// csucs tavolsagaval:
const auto akt_szomszed_tav = g[szomszed.csucs].max_tav + szomszed.tav;
if (akt_csucs.max_tav < akt_szomszed_tav) {
// Ha az aktualis szomszedon keresztul futo ut hossza nagyobb,
// mint az eddig megtalalt leghosszabb ut, akkor az eddigi leghosszabb ut
// lesz a masodik leghosszabb.
akt_csucs.max_tav_max_szomszed_nelkul = akt_csucs.max_tav;
// Az aktualis szomszedon keresztul futo ut lesz a leghosszabb.
akt_csucs.max_tav = akt_szomszed_tav;
akt_csucs.max_szomszed = szomszed.csucs;
} else if (akt_csucs.max_tav_max_szomszed_nelkul < akt_szomszed_tav) {
// Ha az aktualis szomszedon keresztul futo ut hossza kisebb (vagy egyenlo),
// mint az eddig megtalalt leghosszabb ut, de hosszabb, mint
// a masodik leghosszabb, akkor az aktualis szomszedon keresztul
// futo ut lesz a masodik leghosszabb.
akt_csucs.max_tav_max_szomszed_nelkul = akt_szomszed_tav;
}
}
}
}
// A masodik melysegi bejaras soran minden csucshoz kiszamitjuk az onnan kiindulo leghosszabb
// ut hosszat, most mar figyelembe veve a felfele vezeto utakat is.
void dfs_2(int akt, Graf &g) {
auto &akt_csucs = g[akt];
if (akt_csucs.szulo != -1) {
// A gyoker csucs eseten nincs szukseg tovabbi szamolasra, mivel onnan
// csak lefele vezethet ut, azokat pedig mar az elso melysegi bejaras
// soran kiszamitottuk.
const auto &szulo_csucs = g[akt_csucs.szulo];
// Meghatarozzuk a szulo csucs fele vezeto leghosszabb utat. Ennek az
// elso lepese a szulo csucstol valo tavolsag.
auto szulo_max_tav = akt_csucs.szulo_tav;
if (szulo_csucs.max_szomszed == akt) {
// Ha a szulo csucsbol kiindulo leghosszabb ut az aktualis csucson keresztul
// vezet, akkor a szulo csucs masodik leghosszabb utjat hasznalhatjuk csak.
szulo_max_tav += szulo_csucs.max_tav_max_szomszed_nelkul;
} else {
// A szulo csucsbol kiindulo leghosszabb ut nem az aktualis csucson keresztul
// vezet, ezert azt hasznaljuk.
szulo_max_tav += szulo_csucs.max_tav;
}
if (akt_csucs.max_tav < szulo_max_tav) {
// Ha az eddig megtalalt leghosszabb lefele vezeto ut hossza kisebb,
// mint a szulo fele vezeto ut, akkor szulo fele vezeto lesz a leghosszabb.
// A cserevel 'felszabadul' az eddig lefele tarto leghosszabb uthoz tartozo el,
// igy az el masik vegen levo csucs a szulo fele vezeto ut kiakakitasa soran mar
// a max_tav-ot hasznalhatja, es nem kell a masodlagos utvonallal
// (max_tav_max_szomszed_nelkul) 'beernie'.
akt_csucs.max_tav = szulo_max_tav;
// Ha a leghosszabb uthoz tartozo szomszed a szulo csucs lesz, akkor mar nincs
// szukseg a masodlagos utvonal hosszanak (max_tav_max_szomszed_nelkul)
// a frissitesere, mivel ezzel a lepessel felszabadul az eddig lefele vezeto
// utvonalhoz tartozo el, igy mar tobbet nem lesz szukseg a masodlagos utvonalra.
akt_csucs.max_szomszed = akt_csucs.szulo;
} else if (akt_csucs.max_tav_max_szomszed_nelkul < szulo_max_tav) {
// Ha a szulo fele vezeto ut hossza kisebb (vagy egyenlo), mint az eddig megtalalt
// leghosszabb ut, de nagyobb, mint a masodlagos ut hossza, akkor a masodlagos
// utvonalat lecsereljuk a szulo iranyaba menore.
akt_csucs.max_tav_max_szomszed_nelkul = szulo_max_tav;
}
}
for (const auto &szomszed : akt_csucs.szomszedok) {
if (szomszed.csucs != akt_csucs.szulo) {
// Feldolgozuk az egy szinttel lejjebb levo csucsokat.
dfs_2(szomszed.csucs, g);
}
}
}
// Feldolgozza a korabban beolvasott elek listajat.
void feldolgoz(const std::vector<El> &elek) {
// A fa-graf csucsainak a szama egyenlo az elek szama + 1-gyel.
const auto n = elek.size() + 1;
Graf g(n);
// Letrehozzuk a szomszedsagi listat.
for (const auto &e : elek) {
// Az 'El' strukturaban talahato csucs indexek 1-tol szamozodnak,
// ezert mindenhonnan ki kell vonni beloluk egyet.
g[e.honnan - 1].szomszedok.emplace_back(e.hova - 1, e.tav);
g[e.hova - 1].szomszedok.emplace_back(e.honnan - 1, e.tav);
}
// Kiszamitjuk minden csucshoz az onnan kiindulo leghosszabb es masodik leghosszabb
// lefele meno utakat.
dfs_1(0, g);
// Kiszamitjuk minden csucshoz az onnan kiindulo leghosszabb utat.
dfs_2(0, g);
// Meghatarozzuk a leghosszabb utak kozul a legrovidebbet.
const auto min_tav = std::min_element(g.cbegin(), g.cend(), [](const Csucs &a, const Csucs &b) {
return a.max_tav < b.max_tav;
})->max_tav;
// Kivalogatjuk azoknak a csucsoknak az indexet, amelyebol a leghosszabb kiindulo ut
// hossza minimalis.
std::vector<size_t> min_helyek;
for (auto i = 0u; i < n; i++) {
if (g[i].max_tav == min_tav) {
// A kimenetben a csucsok 1-tol szamozodnak, ezert mindegyik
// indexhez hozzaadunk egyet.
min_helyek.push_back(i + 1);
}
}
using std::cout;
// Kiiratjuk az eredmenyt a standard kimenetre.
cout << min_tav << '\n';
cout << min_helyek.size() << '\n';
for (auto i : min_helyek) {
cout << i << ' ';
}
cout << '\n';
}
int main() {
const auto elek = beolvas(std::cin);
feldolgoz(elek);
return 0;
}