var f,g:text;
sus,jos,i,j,x,y,z,n,m,cat:integer;
a,viz:array[1..100,1..100]of integer;
{procedure cauta(nr:integer);
var i:integer;
begin
if nr=n then inc(jos)
else begin
for i:=1 to n do if (a[nr,i]<>0)and(viz[nr,i]=0)then begin viz[nr,i]:=1;
                                                         sus:=sus+a[nr,i];
                                                         writeln(nr);
                                                         for j:=1 to i do viz[j,i]:=0;
                                                         for j:=i+1 to n do viz[i,j]:=0;
                                                         cauta(i);
                                                         end;
end;
end;  }
begin
assign(f,'tunel.in');
assign(g,'tunel.out');
reset(f);
rewrite(g);
readln(f,n,m);
for i:=1 to m do begin readln(f,x,y,z);
                       a[x,y]:=z;
                       a[y,x]:=z;
                       if (x<>n)and(y<>n)then inc(cat,z*4);
                 end;
cat:=cat+a[n-1,n];
writeln(g,cat);
close(f);
close(g);
end.