var n,m,i,j,k,d,x:longint; v:array[1..100,1..100] of longint; c,t,u,a:array[1..100] of longint; f,g:text;
begin
        assign(f,'dijkstra.in');
        assign(g,'dijkstra.out');
        reset(f);
        rewrite(g);
        read(f,n,m);
        for i:=1 to n do
                for j:=1 to n do v[i,j]:=1000;
        for k:=1 to m do begin
                read(f,i,j,d);
                v[i,j]:=d;
        end;
        read(f,d);
        t[d]:=d;
        for i:=1 to n do c[i]:=1000;
        c[d]:=0;
        for k:=1 to m do begin
                x:=1000;
                for j:=1 to n do if (c[j]<x) and (a[j]=0) then begin
                        i:=j;
                        x:=c[j]
                end;
                for j:=1 to n do if c[j]>c[i]+v[i,j] then begin
                        c[j]:=c[i]+v[i,j];
                        t[j]:=i;
                end;
                a[i]:=1;
        end;
        for k:=1 to n do if k<>d then begin
                writeln(g,'distanta de la nodul ',d,' la nodul ',k,' este: ',c[k]);
                write(g,'drumul este: ');
                i:=k;
                u[1]:=k;
                j:=2;
                while t[i]<>d do begin
                        u[j]:=t[i];
                        i:=t[i];
                        inc(j);
                end;
                u[j]:=d;
                for i:=j downto 1 do write(g,u[i],' ');
                writeln(g);
        end;
        close(g);
end.