const oo=1000000000;
var
n,m,i,j,a,b,c,num,min,t:longint;
dist,first:array[1..30005]of longint;
flag:array[1..30005]of boolean;
edge:array[1..150005]of record b,c,next:longint; end;

procedure add(a,b,c:longint);
begin
  inc(t);
  edge[t].b:=b; edge[t].c:=c; edge[t].next:=first[a];
  first[a]:=t;
end;

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

  readln(n,m);
  for i:=2 to n do dist[i]:=oo;
  for i:=1 to m do
  begin
    readln(a,b,c);
    add(a,b,c);
  end;
  flag[1]:=true; j:=first[1];
  while j<>0 do
  begin
    if edge[j].c<dist[edge[j].b] then dist[edge[j].b]:=edge[j].c;
    j:=edge[j].next;
  end;
  for i:=2 to n do
  begin
    min:=oo;
    for j:=1 to n do if not flag[j] and (dist[j]<min) then
    begin
      num:=j;
      min:=dist[j];
    end;
    if num=n then begin writeln(min); halt; end;
    flag[num]:=true;
    j:=first[num];
    while j<>0 do
    begin
      if not flag[j] and (min+edge[j].c<dist[edge[j].b]) then
        dist[edge[j].b]:=min+edge[j].c;
      j:=edge[j].next;
    end;
  end;

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