program zavod;

const maxN = 1000000;
      maxM = 1000000;
      zacatek = 2;  { prohodili jsme startovní a cílove město, abychom }
      konec = 1;    { nemuseli otáčet cestu }

var M,N:integer;

    mesta: array [1..maxN] of record { informace o mestech }
            vzdalenost : integer;   { počet etap od začátku }
            maxDivaku : integer;    { počet diváků, který shlédne trasu až sem}
            predchozi:integer;      { předchozí město na nejlepší trase }
            stupen: integer;        { počet sousedních měst}
            zacatek: integer;       { pozice prvního souseda v poli sousede }
            pozice:integer; {dočasná hodnota používaná při načítání}
        end;
    sousede: array[1..2*maxM] of record {pole sousedů. nejprve jsou uloženi }
                { sousedé města 1, pak sousedé města 2, atd. }
            mesto, divaku:integer;
        end;
    hrany: array[1..maxM] of record   { pole hran, neboli možných etap. Použito}
                                      { jen při načítání. }
        odkud, kam, divaku: integer;  { odkud a kam etapa vede a počet diváků }
        end;

{ Načtení dat ze vstupu - naplní pole mesta a sousede. }
procedure nacti;
var i, pozice:integer;
    a,b, divaku:integer; {města}
    p:integer;
begin
    readln(N, M);
    for i := 1 to N do begin
        mesta[i].stupen := 0;
    end;
    {načti hrany a spočti stupně}
    for i:= 1 to M do begin
        readln(a, b, hrany[i].divaku);
        hrany[i].odkud := a; hrany[i].kam := b;
        mesta[a].stupen := mesta[a].stupen + 1;
        mesta[b].stupen := mesta[b].stupen + 1;
    end;
    { urči začátky pro jednotlivá města v poli sousede }
    pozice := 1; {pruběžná pozice v poli sousede}
    for i := 1 to N do begin
        mesta[i].zacatek := pozice;
        mesta[i].pozice := pozice;
        pozice := pozice + mesta[i].stupen;
    end;
    { naplň pole sousede }
    for i:= 1 to M do begin
        a := hrany[i].odkud; b := hrany[i].kam; divaku := hrany[i].divaku;
        {přidej souseda městu a}
        p:= mesta[a].pozice;
        sousede[p].mesto := b;
        sousede[p].divaku := divaku;
        mesta[a].pozice := p+ 1;
        {přidej souseda městu b}
        p:= mesta[b].pozice;
        sousede[p].mesto := a;
        sousede[p].divaku := divaku;
        mesta[b].pozice := p+ 1;
    end;

end;

{ Fronta měst ke zpracování. Vzhledem ke způsobu přidávání platí, že }
{ město s nižší vzdáleností od začátku je v poli na nižší pozici než }
{ město s vétší vzdáleností. }
var fronta: array[1..maxN] of integer;
    zacF,konF:integer; {začátek a konec fronty}

{ Projde sousedy vybraného města a pokusí se prodloužit do nich trasu. }
procedure projdiSousedy(mesto:integer);
var i: integer; {index do pole sousedů}
    posledni: integer; {index posledního souseda v poli sousede. }
    divaku, soused : integer;
begin
    posledni := mesta[mesto].zacatek + mesta[mesto].stupen - 1;
    for i:= mesta[mesto].zacatek to posledni do begin
        divaku := mesta[mesto].maxDivaku + sousede[i].divaku;
        soused := sousede[i].mesto;
        if mesta[soused].vzdalenost = -1 then begin
            {město jsme ještě nenavštívili.}
            konF := konF + 1;
            fronta[konF] := soused; {dej do fronty}
            mesta[soused].vzdalenost := mesta[mesto].vzdalenost + 1;
            mesta[soused].maxDivaku := divaku; { a toto je zatim nejlepší trasa}
            mesta[soused].predchozi := mesto;
        end else if (mesta[soused].vzdalenost = mesta[mesto].vzdalenost + 1)
            and (mesta[soused].maxDivaku < divaku) then begin
            { trasa pšes toto město je lepší, přenastavíme hodnoty u souseda.}
            mesta[soused].maxDivaku := divaku;
            mesta[soused].predchozi := mesto;
        end;
    end;
end;

{ Spočte hodnoty maxDivaku, vzdalenost a predchozi v poli mesta, čímž }
{ prakticky vyřeší celou úlohu. }
procedure spocti;
var mesto: integer;
    i:integer;
begin
    {inicializace}
    for i := 1 to N do begin
        mesta[i].maxDivaku := 0;
        mesta[i].vzdalenost := -1; {zatim jsme nikde nebyli}
    end;
    {počáteční město má vzdálenost 0 a žádné diváky}
    mesta[zacatek].vzdalenost := 0;
    mesta[zacatek].maxDivaku := 0;
    fronta[1] := zacatek;
    zacF := 1; konF := 1;
    {dokud není fronta prazdná}
    while zacF <= konF do begin
        mesto := fronta[zacF];
        zacF := zacF + 1;  {přečti hodnotu z fronty}
        projdiSousedy(mesto);
    end;
end;

{ Vypíše cestu od konce do začátku. Protože cesta, kterou najde spocti(), }
{ končí ve Vyšných Hacích, tak je vysledkem přesně to, co požaduje zadání. }
procedure vypis;
var mesto:integer;
begin
    writeln(mesta[konec].vzdalenost, ' ', mesta[konec].maxDivaku);
    mesto := konec;
    write(konec);
    while mesto <> zacatek do begin   {dokud nejsme na začátku}
        mesto := mesta[mesto].predchozi; {najdi město, ze kterého jsme příšli}
        write(' ', mesto);       {vypiš ho}
    end;
    writeln;
end;


{ Hlavní program }
begin
    nacti;
    spocti;
    vypis;
end.