program Project1;
type heap=record
id:integer;
nm:longint;
end;
var inheap:array[0..30000]of boolean;
heappos:array[0..30000]of integer;
h:array[0..30000]of heap;
map,mindis:array[0..30000,0..30000]of integer;
g:array[0..30000,0..8000]of integer;
x,y,z,min,i,j,k,size,n,m,q:longint;
procedure swap(var i,j:heap);
var t:heap;
begin
t:=i;
i:=j;
j:=t;
end;
//----------------------------------------------
procedure down(x:longint);
var y:longint;
begin
if (x*2<=size)and(h[x*2].nm<h[x].nm) then y:=x*2 else y:=x;
if (x*2+1<=size)and(h[x*2+1].nm<h[y].nm) then y:=x*2+1;
if y<>x then
begin
heappos[h[x].id]:=y;
heappos[h[y].id]:=x;
swap(h[y],h[x]);
down(y);
end;
end;
//----------------------------------------------
procedure up(x:longint);
begin
while (x>1)and(h[x].nm<h[x shr 1].nm) do
begin
heappos[h[x].id]:=x shr 1;
heappos[h[x shr 1].id]:=x;
swap(h[x],h[x shr 1]);
x:=x shr 1;
end;
end;
//----------------------------------------------
procedure getmin(var min,id:longint);
begin
min:=h[1].nm; id:=h[1].id;
heappos[h[1].id]:=size;
heappos[h[size].id]:=1;
swap(h[1],h[size]);
dec(size);
end;
//---------------------------------------------
procedure dijkstra(f:longint);
begin
size:=n;
for i:=1 to n do
begin
h[i].nm:=maxlongint shr 2;
heappos[i]:=i;
h[i].id:=i;
end;
fillchar(inheap,sizeof(inheap),0);
h[f].nm:=0;
up(f);
for i:=1 to n do
begin
getmin(min,k);
inheap[k]:=true;
mindis[f,k]:=min; mindis[k,f]:=min;
down(1);
for j:=1 to g[k,0] do
begin
q:=g[k,j];
if not inheap[q] and(h[heappos[q]].nm>min+map[k,q])
then begin
h[heappos[q]].nm:=min+map[k,q];
up(heappos[q]);
end;
end;
end;
end;
//--------------------------------------------------
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to m do
begin
readln(x,y,z);
inc(g[x,0]); g[x,g[x,0]]:=y;
inc(g[y,0]); g[y,g[y,0]]:=x;
map[x,y]:=z; map[y,x]:=z;
end;
dijkstra(1);
writeln(mindis[1,n]);
close(input);
close(output);
end.