#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1000001;
const int IMAX=2000000000;
int queue[MAXN];
struct node
{
	int u,v,w;
}map[MAXN];
int dist[MAXN];
int vis[MAXN];
int n,m;
int a,b,cnt;

int find(int u,int v)
{
	for(int i=1;i<=m;i++)
		if(map[i].u==u&&map[i].v==v)
			return map[i].w;
	return IMAX;
}

void SPFA(int v0)
{
    for(int i=1;i<=n;i++)
        dist[i]=IMAX;
    dist[v0]=0;
    vis[v0]=1;
    queue[0]=v0;
    int begin=0,end=1;
    while(begin<end)
    {
        int p=queue[begin];
        for(int i=1;i<=n;i++)
        {
            if(dist[p]+find(p,i)<dist[i])
            {
                dist[i]=dist[p]+find(p,i);
                if(vis[i]==0)
                {
                    queue[end++]=i;
                    vis[i]=1;
                }
            }
        }
        begin++;
        vis[p]=0;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
            map[i].w=IMAX;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&map[i].u,&map[i].v,&cnt);
        map[i].w=min(map[i].w,cnt);
    }
    cnt=0;
    for(int i=2;i<=n;i++)
    {
    	SPFA(i);
    	cnt+=dist[1];
    	SPFA(1);
    	cnt+=dist[i];
	}
    printf("%d\n",cnt);
    return 0;
}