type arr=array[1..1000,1..1000]of longint;var n,m,i,j,x,y,ans:longint; a,b:arr; d:array[1..1000]of longint; f:array[1..1000]of boolean;PRocedure dij;var i,j,u,min:longint;begin fillchar(f,sizeof(f),true); fillchar(d,sizeof(d),$7f); for i:=2 to n do if f[i] then d[i]:=a[1,i]; repeat u:=0;min:=d[1]; for i:=2 to n do if f[i] and(d[i]<min) then begin min:=d[i]; u:=i; end; if u>0 then begin f[u]:=false; ans:=ans+d[u]; for i:=2 to n do if f[i] and(d[i]>d[u]+a[u,i]) then d[i]:=d[u]+a[u,i]; end; until u=0;end;procedure dij2;var i,j,u,min:longint;begin fillchar(f,sizeof(f),true); fillchar(d,sizeof(d),$7f); for i:=2 to n do if f[i] then d[i]:=b[1,i]; repeat u:=0;min:=d[1]; for i:=2 to n do if f[i] and(d[i]<min) then begin min:=d[i]; u:=i; end; if u>0 then begin f[u]:=false; ans:=ans+d[u]; for i:=2 to n do if f[i] and(d[i]>d[u]+b[u,i]) then d[i]:=d[u]+b[u,i]; end; until u=0;end;begin readln(n,m); fillchar(a,sizeof(a),$7f); fillchar(b,sizeof(b),$7f); for i:=1 to m do begin readln(x,y,j); if a[x,y]>j then a[x,y]:=j; if b[y,x]>j then b[y,x]:=j; end; dij; dij2; writeln(ans);end.
