program block;

type

  point=^node;

    node=record

    v,c:longint; next:point; end;

var

  a:array[..]of point;

  dis:array[..,..]of longint;

  q:array[..]of longint;

  g:array[..]of boolean;

  e:array[..,..]of longint;

  n,i,m,x,y,v,ans:longint;  p:point;

procedure add(x,y,c:longint);

var p:point;

begin

  new(p); p^.v:=y; p^.c:=c; p^.next:=a[x];  a[x]:=p;

end;

procedure spfa(s,d,l:longint);

var i,h,t,u,v,k:longint;

begin

  fillchar(g,sizeof(g),false);

  for i:= to n do dis[i,l]:=maxlongint div ;  dis[s,l]:=; g[s]:=true;

  h:=; t:=; q[]:=s;

  while h<t do

   begin

     inc(h); u:=q[h]; g[u]:=false; new(p); p:=a[u];

     while p<>nil do

     begin

       v:=p^.v;

       if dis[v,l]>dis[u,l]+p^.c then

        begin

          dis[v,l]:=dis[u,l]+p^.c;

          if g[v]=false then begin g[v]:=true; inc(t);q[t]:=v;end;

        end;

       p:=p^.next;

     end;

   end;

end;

begin

  assign(input,'block.in');

  reset(input);

  assign(output,'block.out');

  rewrite(output);

  readln(n,m);

  for i:= to m do

   begin

     readln(x,y,v);  e[i,]:=x; e[i,]:=y; e[i,]:=v;

     add(x,y,v); add(y,x,v);

   end;

  spfa(,n,); spfa(n,,); ans:=maxlongint;

  for i:= to m do

   begin

    v:=dis[e[i,],]+dis[e[i,],]+e[i,];   if (v<ans)and(v>dis[n,]) then ans:=v;

    v:=dis[e[i,],]+dis[e[i,],]+e[i,];   if (v<ans)and(v>dis[n,]) then ans:=v;

   end;

  writeln(ans);

  close(input); close(output);

end.