var
   i,j,k:longint;
   n,m:longint;
   fa,d:array[0..300]of longint;
   a:array[1..300,1..300]of longint;
   q,ww:array[1..1000]of longint;
   tt,ans1,ans2,x,y,t:longint;
   v:array[1..300]of boolean;

procedure swap(var xx,yy:longint);
var t:longint;
begin
     t:=xx;xx:=yy;yy:=t;
end;

procedure insert(xx,yy:longint);
var i,j:longint;
begin
     inc(tt);
     q[tt]:=xx;ww[tt]:=yy;
     j:=tt;i:=j shr 1;
     while i>0 do
     begin
          if ww[i]>ww[j] then
          begin
               swap(q[i],q[j]);
               swap(ww[i],ww[j]);
               j:=i;i:=i shr 1;
          end
          else break;
     end;
end;

procedure delete;
var i,j:longint;
begin
     q[1]:=q[tt];ww[1]:=ww[tt];
     dec(tt);
     j:=1;i:=j shl 1;
     while i<=tt do
     begin
          if (i<tt)and(ww[i]>ww[i+1]) then inc(i);
          if ww[i]>ww[j] then
          begin
               swap(q[i],q[j]);
               swap(ww[i],ww[j]);
               j:=i;i:=i shl 1;
          end
          else break;
     end;
end;

procedure dij;
var x,y,i,j:longint;
begin
     d[1]:=0;
     tt:=0;
     insert(1,0);
     fillchar(v,sizeof(v),0);
     while tt<>0 do
     begin
          x:=q[1];
          y:=ww[1];
          delete;
          if v[x] then continue
          else v[x]:=true;
          for i:=1 to n do
          if (i<>x)and(a[x,i]<>0) then
          begin
               if d[i]>d[x]+a[x,i] then
               begin
                    d[i]:=d[x]+a[x,i];
                    fa[i]:=x;
                    insert(i,d[i]);
               end;
          end;
     end;
end;

procedure dij1;
var x,y,i,j:longint;
begin
     for i:=1 to n do d[i]:=maxlongint shr 1;
     d[1]:=0;
     tt:=0;
     insert(1,0);
     fillchar(v,sizeof(v),0);
     while tt<>0 do
     begin
          x:=q[1];
          y:=ww[1];
          delete;
          if v[x] then continue
          else v[x]:=true;
          for i:=1 to n do
          if (i<>x)and(a[x,i]<>0) then
          begin
               if d[i]>d[x]+a[x,i] then
               begin
                    d[i]:=d[x]+a[x,i];
                  //  fa[i]:=x;
                    insert(i,d[i]);
               end;
          end;
     end;
end;

function max(x,y:longint):longint;
begin
     if x>y then exit(x);exit(y);
end;

begin
     assign(input,'rblock.in');
     reset(input);
     assign(output,'rblock.out');
     rewrite(output);

     readln(n,m);
     fillchar(a,sizeof(a),0);
     fillchar(fa,sizeof(fa),0);
     for i:=1 to m do
     begin
          readln(x,y,t);
          a[x,y]:=t;
          a[y,x]:=t;
     end;
     for i:=1 to n do d[i]:=maxlongint shr 1;
     dij;
     ans1:=d[n];ans2:=0;
     x:=fa[n];
     a[n,fa[n]]:=a[n,fa[n]]shl 1;
     a[fa[n],n]:=a[n,fa[n]];
     dij1;
     ans2:=max(ans2,d[n]);
     a[n,fa[n]]:=a[n,fa[n]]shr 1;
     a[fa[n],n]:=a[n,fa[n]];
     while fa[x]<>0 do
     begin
          a[x,fa[x]]:=a[x,fa[x]]shl 1;
          a[fa[x],x]:=a[x,fa[x]];
          dij1;
          ans2:=max(ans2,d[n]);
          a[x,fa[x]]:=a[x,fa[x]]shr 1;
          a[fa[x],x]:=a[x,fa[x]];
          x:=fa[x];
     end;

     writeln(ans2-ans1);

     close(input);close(output);
end.