#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E3+5;
const int INF = 0x3f3f3f3f;
int n,m;
int mp[N][N];
int mirror[N][N];
int dis[N];
bool visited[N];
long long sum;

void diji(int (*p)[N])
{
    memset(dis,0x3f,sizeof(dis));
    memset(visited,false,sizeof(visited));
    for(int i=1; i<=n; i++){
        dis[i]=p[1][i];
    }
    dis[1]=0;
    visited[1]=true;
    for(int i=1; i<n; i++){
        int k,minn=INF;
        for(int j=1; j<=n; j++){
            if(dis[j]<minn && !visited[j]){
                minn=dis[j],k=j;
            }
            visited[k]=true;
            for(int j=1; j<=n; j++){
                if(!visited[j] && dis[j]>dis[k]+p[k][j]){
                    dis[j]=dis[k]+p[k][j];
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    memset(mirror,0x3f,sizeof(mirror));
    for(int i=1; i<=m; i++){
        cin >> u >> v >> w;
        if(mp[u][v]>w){
            mp[u][v]=w;
            mirror[v][u]=w;
        }
    }
    diji(mp);
    for(int i=1; i<=n; i++){
        sum += dis[i];
    }
    diji(mirror);
    for(int i=1; i<=n; i++){
        sum += dis[i];
    }
    cout << sum;
    return 0;
}