const x='v341.in';
y='v341.out';
type treenode=record
a,b,son:longint;
end;
var map:array[1..300000]of treenode;
path:array[1..30000]of longint;
dis:array[1..30000]of longint;
line:array[1..30000]of longint;
i,j,k,m,n,top,rear,p1,p2,p3:longint;
begin
readln(n,m);
for i:=1 to n do
dis[i]:=maxlongint;
dis[1]:=0;
for i:=1 to m do
begin
readln(p1,p3,p2);
map[i].a:=p3;
map[i].b:=p2;
map[150000+i].a:=p1;
map[150000+i].b:=p2;
if path[p1]=0
then
path[p1]:=i
else
begin
map[i].son:=path[p1];
path[p1]:=i;
end;
if path[p3]=0
then
path[p3]:=150000+i
else
begin
map[150000+i].son:=path[p3];
path[p3]:=150000+i;
end;
end;
top:=0;
rear:=1;
line[1]:=1;
while top<>rear do
begin
top:=(top+1)mod n;
k:=path[line[top]];
while k<>0 do
begin
if dis[line[top]]+map[k].b<dis[map[k].a]
then
begin
rear:=(rear+1)mod n;
line[rear]:=map[k].a;
dis[map[k].a]:=dis[line[top]]+map[k].b;
end;
k:=map[k].son;
end;
end;
writeln(dis[n]);
end.