记录编号	39405	评测结果	AAAAAAAAAA
题目名称	三元限制最短路	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.699 s
提交时间	2012-07-10 13:00:58	内存使用	123.22 MiB

program patha;
const maxn=1001; maxtot=5000000;
var
 pre,xx,yy,step,link,next:array[0..maxtot] of longint;
 aa,a:array[0..maxn,0..maxn] of longint;
 v:array[0..maxn,0..maxn] of boolean;
 n,i,x,y,z,tot,m,k,j,l,h,t:longint;
 procedure print(k:longint);
 begin
  if pre[k]=0 then
   begin
    write(1,' ',yy[k]);
    exit;
   end;
  print(pre[k]);
  write(' ',yy[k]);
 end;
 procedure bfs;
 begin
  h:=0; t:=0;
  for i:=1 to n do
   if a[1,i]<>0 then
    if not v[1,i] then
     begin
      inc(t);
      xx[t]:=1; yy[t]:=i; step[t]:=1;
      pre[t]:=0;
      v[1,i]:=true;
      if yy[t]=n then
       begin
        writeln(step[t]);
        print(t);
        close(input); close(output);
        halt;
       end;
     end;
   repeat
    h:=h+1;
    i:=a[xx[h],yy[h]];
    while i<>0 do
     begin
      if not v[yy[h],link[i]] then
       begin
        v[yy[h],link[i]]:=true;
        inc(t); pre[t]:=h;
        xx[t]:=yy[h]; yy[t]:=link[i];
        step[t]:=step[h]+1;
        if yy[t]=n then
         begin
          writeln(step[t]);
          print(t);
          close(input); close(output);
          halt;
         end;
       end;
      i:=next[i];
     end;
   until h>=t;
 end;
 procedure insert(x,y:longint);
 begin
  inc(aa[x,0]); aa[x,aa[x,0]]:=y;
 end;
 procedure delete(x,y,z:longint);
 var i,fa:longint;
 begin
  i:=a[x,y];
  if link[i]=z then
   begin
    a[x,y]:=next[i];
    exit;
   end;
  fa:=i;
  while i<>0 do
   begin
    if link[i]=z then
     begin
      next[fa]:=next[i];
      exit;
     end;
    fa:=i;
    i:=next[i];
   end;
 end;
 procedure init(x,y,z:longint);
 begin
  inc(tot); next[tot]:=a[x,y];
  a[x,y]:=tot; link[tot]:=z;
 end;
begin
 assign(input,'patha.in'); reset(input);
 assign(output,'patha.out'); rewrite(output);
 readln(n,m,k);
 fillchar(aa,sizeof(aa),0);
 for i:=1 to m do
  begin
   readln(x,y);
   insert(x,y);
   insert(y,x);
  end;
 fillchar(xx,sizeof(xx),0);
 yy:=xx; link:=yy;
 for i:=1 to n do
  for j:=1 to aa[i,0] do
   for l:=1 to aa[aa[i,j],0] do
    init(i,aa[i,j],aa[aa[i,j],l]);
 for i:=1 to k do
  begin
   readln(x,y,z);
   delete(x,y,z);
  end;
 bfs;
 close(input); close(output);
end.