//Dijkstra complet lungimi+drumuri
//un singur varf de plecare -> start ; drumuri catre celelalte n-1 noduri
//O(n^2)
//40p infoarena
{$Q-}
program dijkkk;
type vect=array[1..5000]of longint;
     mat=array[1..5000,1..5000]of longint;
const infinit=maxint;
var d,pre,m:vect;c:mat;
    n,muchii,start:integer;
    f,g:text;
    intrare,iesire:array[1..1 shl 17] of char;

procedure initializare;
var i,j,x,y,cost:longint;
begin
readln(f,n,muchii);start:=1;
for i:=1 to n do
 for j:=1 to n do begin c[i,j]:=infinit; c[j,i]:=infinit;end;
for i:=1 to muchii do begin
                    readln(f,x,y,cost);
                    c[x,y]:=cost;
                    end;
for i:=1 to n do begin d[i]:=c[start,i]; pre[i]:=start;end;
m[start]:=1;pre[start]:=0;
end;

procedure asfalteaza;
var i,j,dmin,vfmin:longint;
begin
for j:=1 to n do
   begin
   dmin:=infinit;
   for i:=1 to n do
     if (m[i]=0)and(dmin>d[i]) then begin
                                    dmin:=d[i];
                                    vfmin:=i;
                                    end;
   m[vfmin]:=1;
   for i:=1 to n do
    if (m[i]=0)and(d[i]>dmin+c[vfmin,i]) then
                                             begin
                                             pre[i]:=vfmin;
                                             d[i]:=dmin+c[vfmin,i];
                                             end;
   end;
end;

procedure afiseaza;
var i,j,lg:longint;
    dr:vect;
begin
for i:=1 to n do
if i<>start then begin
                 writeln(g,'Costul drumului de cost minim de la ',start,' la ',i,' este: ',d[i]);
                 writeln(g,'Drumul de cost minim:');
                 dr[0]:=i; lg:=0;
                 while pre[dr[lg]]<>0 do
                      begin
                      inc(lg);
                      dr[lg]:=pre[dr[lg-1]];
                      end;
                  for j:=lg downto 0 do write(g,dr[j],' ');
                  writeln(g);
                  end;
end;

begin
assign(f,'dijkstra.in');reset(f);   settextbuf(f,intrare);
assign(g,'dijkstra.out');rewrite(g);settextbuf(g,iesire);
initializare;
asfalteaza;
afiseaza;
close(f);close(g);
end.