const
  maxn=maxlongint div 2;
type
  ar=^node;
  node=record
    a,b:longint;
    next:ar;
  end;
var
  map:array[1..1003,1..1003] of longint;
  fee:array[1..1003] of ar;
  dis,f:array[1..1003] of longint;
  que:array[1..10000] of longint;
  used:array[1..1003] of boolean;
  n,m,s,t:longint;
procedure add(i,j,c,k:longint);
var p:ar;
begin
  map[i,j]:=k;
  new(p);
  with p^ do begin
    a:=j; b:=c; next:=fee[i];
  end;
  fee[i]:=p;
  new(p);
  with p^ do begin
    a:=i; b:=c; next:=fee[j];
  end;
  fee[j]:=p;
end;
procedure mark;
var
  p:ar;
  i1,head,tail,i:longint;
begin
  fillchar(f,sizeof(f),0);
  for i1:=1 to n do dis[i1]:=maxn;
  fillchar(used,sizeof(used),false);
  dis[1]:=0; que[1]:=1; used[1]:=true;
  head:=1; tail:=1;
  while head<=tail do begin
    i:=que[head];
    p:=fee[i];
    while p<>nil do begin
      if (dis[i]+p^.b<dis[p^.a])and(map[i,p^.a]>0) then begin
        dis[p^.a]:=dis[i]+p^.b;
        f[p^.a]:=i;
        if not used[p^.a] then begin
          inc(tail);
          que[tail]:=p^.a;
          used[p^.a]:=true;
        end;
      end;
      p:=p^.next;
    end;
    inc(head);
    used[i]:=false;
  end;
end;
procedure main;
var i1,i,j,w1,w2,w3,ans:longint;
begin
  readln(n,m);
  for i1:=1 to m do begin
    readln(w1,w2,w3);
    add(w1,w2,w3,1);
  end;
  add(n,n+1,0,2);
  inc(n);

  ans:=0;
  mark;
  while f[n]<>0 do begin
    inc(ans,dis[n]);
    i:=n;
    repeat
      j:=i; i:=f[i];
      dec(map[i,j]);
      inc(map[j,i]);
    until i=1;
    mark;
  end;
  writeln(ans);
end;
begin
  main;
end.