#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int inf=(1<<31)-1;
int vis[maxn],n,m,head[maxn],k,ans;
int dis[maxn];
struct node{
	int to,next,w;
}e[maxn*2];
struct qnode{
	int id,val;
	qnode(int iid,int ww){id=iid;val=ww;}
	friend bool operator<(qnode q1,qnode q2){
		return q1.val>q2.val;
	}
};
void adde(int u,int v,int w){
	e[++k].to=v;e[k].w=w;
	e[k].next=head[u];head[u]=k;
}
void dij(int s){
	priority_queue<qnode> q;
	for(int i=1;i<=n;i++)dis[i]=inf;
	memset(vis,0,sizeof(vis));
	dis[s]=0;q.push(qnode(s,0));
	while(!q.empty()){
		qnode qn=q.top();q.pop();
		if(vis[qn.id])continue;
		vis[qn.id]=true;
		for(int i=head[qn.id];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]>dis[qn.id]+e[i].w){
				dis[v]=dis[qn.id]+e[i].w;
				q.push(qnode(v,dis[v]));
			}
		}
	}
}
int main(){
	int u,v,w;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	scanf("%d%d%d",&u,&v,&w);
    	adde(u,v,w);
	}
	dij(1);
	for(int i=2;i<=n;i++)ans+=dis[i];
	for(int i=2;i<=n;i++){
		dij(i);
		ans+=dis[1];
	}
	cout<<ans;
	return 0;
}