#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int len;
    int sta;
};

struct pos
{
    int from;
    int to;
    int value;
};

pos p;
edge road[101][101];
int value[101][101];

void update(int from,int to,int x)
{
    if(road[from][to].sta == from)
    {
        value[from][to] += road[from][to].len;
    }
    else
    {
        update(from,x,road[from][x].sta);
        update(x,to,road[x][to].sta);
    }
}

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            road[i][j].len = 1e9+7;
        }
    }
    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        road[x][y].len = z;
        road[x][y].sta = x;
        road[y][x].len = z;
        road[y][x].sta = y;
    }
    for(int i = 1; i <= n; i++)
    {
        road[i][i].len = 0;
        road[i][i].sta = i;
    }
    //第一遍floyd,记录数据
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                int va = road[i][k].len + road[k][j].len;
                if(va < road[i][j].len)
                {
                    road[i][j].len = va;
                    road[i][j].sta = k;//k是中转点
                }
            }

    //统计数据
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            update(i,j,road[i][j].sta);
        }
    }

    //找出最优转送门位置
    p.value = -1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(value[i][j] > p.value)
            {
                p.value = value[i][j];
                p.from = i;
                p.to = j;
            }
        }
    }

    //放置传送门
    road[p.from][p.to].len = 0;
    road[p.to][p.from].len = 0;

    //重新floyd,统计最优结果
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                road[i][j].len = min(road[i][k].len + road[k][j].len,road[i][j].len);
            }
        }
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            ans += road[i][j].len;  
        }
    }
    cout << ans << endl;
    return 0;
}