var
   ver,next,dat:array[0..50005] of longint;
   ans,temp,n,m,tot:longint;
   fa,dist,pro:array[0..255] of longint;
   v:array[0..255] of boolean;
   
function max(xx,yy:longint):longint;
begin
   if xx<=yy then exit(yy);
   exit(xx);
end;

procedure add(xx,yy,tt:longint);
begin
    inc(tot);ver[tot]:=yy;dat[tot]:=tt;next[tot]:=fa[xx];fa[xx]:=tot;
	inc(tot);ver[tot]:=xx;dat[tot]:=tt;next[tot]:=fa[yy];fa[yy]:=tot;
end;
   
procedure init;
var i:longint;
  xx,yy,tt:longint;
begin
	readln(n,m);
	tot:=1;
	for i:=1 to m do
	  begin
	    readln(xx,yy,tt);
		add(xx,yy,tt);
	  end;
end;

procedure prepare;
var i,j,now,k,tt:longint;
begin 
    filldword(dist,sizeof(dist)>>2,maxlongint>>2);
	fillchar(pro,sizeof(pro),0);
	fillchar(v,sizeof(v),1);
	dist[1]:=0;
	  for i:=1 to n do
	    begin
		  tt:=maxlongint>>1;
		  for j:=1 to n do
		    if (v[j]) and (tt>dist[j]) then begin  tt:=dist[j];k:=j;end;
		  v[k]:=false;
		  j:=fa[k];
		  while j<>0 do
		    begin
			  now:=ver[j];
			     if (dist[now]>dist[k]+dat[j]) and (v[now]) then 
				    begin
					   dist[now]:=dist[k]+dat[j];
					   pro[now]:=j;
					end;
			  j:=next[j];
			end;
		end;
end;

procedure dijs;
var i,j,now,k,tt:longint;
 begin 
    filldword(dist,sizeof(dist)>>2,maxlongint>>2);
	fillchar(v,sizeof(v),1);
	dist[1]:=0;
	  for i:=1 to n do
	    begin
		  tt:=maxlongint>>1;
		  for j:=1 to n do
		    if (v[j]) and (tt>dist[j]) then begin  tt:=dist[j];k:=j;end;
		  v[k]:=false;
		  j:=fa[k];
		  while j<>0 do
		    begin
			  now:=ver[j];
			     if (dist[now]>dist[k]+dat[j] ) and (v[now]) then 
					   dist[now]:=dist[k]+dat[j];
			  j:=next[j];
			end;
		end;
end;
procedure main;
var i,j:longint;
begin
   temp:=dist[n];
   ans:=0;
    for i:=2 to n do
	  begin
	     j:=pro[i];
		 dat[j]:=dat[j]*2;
		 dat[j xor 1]:=dat[j xor 1]*2; 
		 dijs;
		 dat[j]:=dat[j]>>1;
		 dat[j xor 1]:=dat[j xor 1]>>1;
		 ans:=max(ans,dist[n]); 
	  end;
	  
  writeln(ans-temp);
end;
 
begin
  assign(input,'rblock.in');reset(input);
  assign(output,'rblock.out');rewrite(output);
  init;prepare;main;
  close(input);close(output);
end.