program drum_minimmmmmmmmmmmmmmm;
const infinit=2000000000;
type mat=array[1..2000,1..2000]of longint;
     mat_adiacenta=array[1..2000,1..2000] of 0..1;
var d:mat; {matricea distantelor (i,j) }
    a:mat_adiacenta;
    n,m,i,j,k,kk,x,y,l,start,finish,dist,minim:longint;
    f,g:text;
function min(a,b:longint):longint;
begin
if a>b then min:=b
       else min:=a;
end;
begin
assign(f,'ubuntzei.in');reset(f);
assign(g,'ubuntzei.out');rewrite(g);
readln(f,n,m);
readln(f,kk);
for i:=1 to n do
  for j:=1 to n do begin d[i,j]:=0;a[i,j]:=0;end;
for i:=1 to m do begin
                 readln(f,x,y,l);
                 d[x,y]:=l; d[y,x]:=l;
                 a[x,y]:=1;a[y,x]:=1;
                 end;
for i:=1 to n do
 for j:=1 to n do
   if (i<>j)and(d[i,j]=0) then d[i,j]:=maxint;
for i:=1 to n do
 for j:=1 to n do
  for k:=1 to n do if (a[i,k]=1)and(a[k,j]=1)then
                 d[i,j]:=min(d[i,j],d[i,k]+d[k,j]);
writeln(g,d[1,n]);
{for i:=1 to n do
begin
for j:=1 to n do write(g,d[i,j]:6,' ');
writeln(g);
end;}
close(f);close(g);
end.