program dijkstra;
 type mat = array[1..5000,1..5000] of integer;
      vect = array[1..100] of integer;
 var a: mat;
     i,j,n,k,x: integer;
     c,d: vect;

 procedure citire(var a: mat; var n: integer);
 var i,j,cost,k: integer;
     f: text;
 begin
   assign(f,'graf.in'); reset(f);
     readln(f,n,x); k:=0; x:=1;
     while not seekeof(f) do begin
       readln(f,i,j,cost);
       a[i,j] := cost;
       if i = x then d[j] := x;
       a[j,i] := cost;
     end;
   Close(f);
 end;

 begin
  FillChar(a, sizeof(a), 127);
  Citire(a,n);
  for i:=1 to n do
    a[i,i] := 0;

  for i:=1 to n do
    c[i] := a[x,i];

  for i:=1 to n do
    for k:=1 to n do
     if c[k] + a[k,i] < c[i] then begin
       c[i] := c[k] + a[k,i];
       d[i] := k;
     end;

 for I:=1 to n do
   write(c[i],' ');
 writeLn;
 for I:=1 to n do
   write(d[i],' ');

 end.