const fi = '';
fo = '';
maxn = 1000;
maxm = maxn*(maxn-1) div 2;
maxc = 20000;
var n,m,k,u,v,c,s,t,z,i,j : longint;
dmin : int64;
trace : array[1..maxn] of longint;
d : array[1..maxn] of int64;
dd : array[1..maxn] of boolean;
a : array[1..maxn,1..maxn] of longint;
res : array[1..maxn] of int64;
begin
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
readln(n,m,k);
for i := 1 to n do
for j := 1 to n do a[i,j] := maxc;
for i := 1 to m do begin
readln(u,v,c);
a[u,v] := c;
a[v,u] := c;
end;
for i := 1 to k do begin
readln(c,s,t);
fillchar(dd,sizeof(dd),false);
for j := 1 to n do d[j] := maxc;
d[s] := 0;
while true do begin
u := 0;
dmin := maxc;
for v := 1 to n do
if not(dd[v]) and (d[v] < dmin) then begin
dmin := d[v];
u := v;
end;
if (u = 0) or (u = t) then break;
dd[u] := true;
for v := 1 to n do
if not(dd[v]) and (d[v] > d[u] + a[u,v]) then begin
d[v] := d[u] + a[u,v];
trace[v] := u;
end;
end;
if c = 0 then writeln(d[t]) else begin
fillchar(res,sizeof(res),0);
z := 0;
while t <> s do begin
inc(z);
res[z] := t;
t := trace[t];
end;
inc(z);
res[z] := s;
write(z,' ');
for j := z downto 1 do write(res[j],' ');
writeln;
end;
end;
close(output);
close(input);
end.
Y29uc3QgICBmaSA9ICcnOwogICAgICAgIGZvID0gJyc7CiAgICAgICAgbWF4biA9IDEwMDA7CiAgICAgICAgbWF4bSA9IG1heG4qKG1heG4tMSkgZGl2IDI7CiAgICAgICAgbWF4YyA9IDIwMDAwOwogCnZhciAgICAgbixtLGssdSx2LGMscyx0LHosaSxqIDogbG9uZ2ludDsKICAgICAgICBkbWluICAgICAgICAgICAgICAgICAgOiBpbnQ2NDsKICAgICAgICB0cmFjZSAgICAgICAgICAgICAgICAgOiBhcnJheVsxLi5tYXhuXSAgICAgICAgIG9mIGxvbmdpbnQ7CiAgICAgICAgZCAgICAgICAgICAgICAgICAgICAgIDogYXJyYXlbMS4ubWF4bl0gICAgICAgICBvZiBpbnQ2NDsKICAgICAgICBkZCAgICAgICAgICAgICAgICAgICAgOiBhcnJheVsxLi5tYXhuXSAgICAgICAgIG9mIGJvb2xlYW47CiAgICAgICAgYSAgICAgICAgICAgICAgICAgICAgIDogYXJyYXlbMS4ubWF4biwxLi5tYXhuXSBvZiBsb25naW50OwogICAgICAgIHJlcyAgICAgICAgICAgICAgICAgICA6IGFycmF5WzEuLm1heG5dICAgICAgICAgb2YgaW50NjQ7CiAKYmVnaW4KICAgICAgICBhc3NpZ24oaW5wdXQsZmkpOwogICAgICAgIHJlc2V0KGlucHV0KTsKICAgICAgICBhc3NpZ24ob3V0cHV0LGZvKTsKICAgICAgICByZXdyaXRlKG91dHB1dCk7CgogICAgICAgIHJlYWRsbihuLG0sayk7CiAgICAgICAgZm9yIGkgOj0gMSB0byBuIGRvCiAgICAgICAgICAgICAgICBmb3IgaiA6PSAxIHRvIG4gZG8gYVtpLGpdIDo9IG1heGM7CiAgICAgICAgZm9yIGkgOj0gMSB0byBtIGRvIGJlZ2luCiAgICAgICAgICAgICAgICByZWFkbG4odSx2LGMpOwogICAgICAgICAgICAgICAgYVt1LHZdIDo9IGM7CiAgICAgICAgICAgICAgICBhW3YsdV0gOj0gYzsKICAgICAgICBlbmQ7CiAgICAgICAgCiAgICAgICAgZm9yIGkgOj0gMSB0byBrIGRvIGJlZ2luCiAgICAgICAgICAgICAgICByZWFkbG4oYyxzLHQpOwogICAgICAgICAgICAgICAgZmlsbGNoYXIoZGQsc2l6ZW9mKGRkKSxmYWxzZSk7CiAgICAgICAgICAgICAgICBmb3IgaiA6PSAxIHRvIG4gZG8gZFtqXSA6PSBtYXhjOwogICAgICAgICAgICAgICAgZFtzXSA6PSAwOwogICAgICAgICAgICAgICAgd2hpbGUgdHJ1ZSBkbyBiZWdpbgogICAgICAgICAgICAgICAgICAgICAgICB1IDo9IDA7CiAgICAgICAgICAgICAgICAgICAgICAgIGRtaW4gOj0gbWF4YzsKICAgICAgICAgICAgICAgICAgICAgICAgZm9yIHYgOj0gMSB0byBuIGRvCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgbm90KGRkW3ZdKSBhbmQgKGRbdl0gPCBkbWluKSB0aGVuIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkbWluIDo9IGRbdl07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1IDo9IHY7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgICAgICBpZiAodSA9IDApIG9yICh1ID0gdCkgdGhlbiBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgZGRbdV0gOj0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgZm9yIHYgOj0gMSB0byBuIGRvCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgbm90KGRkW3ZdKSBhbmQgKGRbdl0gPiBkW3VdICsgYVt1LHZdKSB0aGVuIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkW3ZdIDo9IGRbdV0gKyBhW3Usdl07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0cmFjZVt2XSA6PSB1OwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICAgICAgICAgIGlmIGMgPSAwIHRoZW4gd3JpdGVsbihkW3RdKSBlbHNlIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgIGZpbGxjaGFyKHJlcyxzaXplb2YocmVzKSwwKTsKICAgICAgICAgICAgICAgICAgICAgICAgeiA6PSAwOwogICAgICAgICAgICAgICAgICAgICAgICB3aGlsZSB0IDw+IHMgZG8gYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbmMoeik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzW3pdIDo9IHQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdCA6PSB0cmFjZVt0XTsKICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgICAgICBpbmMoeik7CiAgICAgICAgICAgICAgICAgICAgICAgIHJlc1t6XSA6PSBzOwogICAgICAgICAgICAgICAgICAgICAgICB3cml0ZSh6LCcgJyk7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvciBqIDo9IHogZG93bnRvIDEgZG8gd3JpdGUocmVzW2pdLCcgJyk7CiAgICAgICAgICAgICAgICAgICAgICAgIHdyaXRlbG47CiAgICAgICAgICAgICAgICBlbmQ7CiAgICAgICAgZW5kOwogICAgICAgIAogICAgICAgIGNsb3NlKG91dHB1dCk7CiAgICAgICAgY2xvc2UoaW5wdXQpOwplbmQuCiAKIAogCg==