只有传送门那条边当作中转站才会影响最短路，所以可以少枚举一维中转站

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int n,m;
int g[N][N],f[N][N];

void back()
{
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            f[i][j] = g[i][j];
}

int main()
{
    memset(g,0x3f,sizeof g);

    cin>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = c;
    }

    //先做一遍floyd
    for(int k = 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                g[i][j] = min(g[i][j],g[i][k]+g[k][j]);

    int ans = 1e9;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<i;j++)
        {
            back();
            f[i][j] = f[j][i] = 0;
            for(int x = 1;x<=n;x++)
                for(int y = 1;y<=n;y++)
                    f[x][y] = min(f[x][y],f[x][i]+f[i][y]);
            for(int x = 1;x<=n;x++)
                for(int y = 1;y<=n;y++)
                    f[x][y] = min(f[x][y],f[x][j]+f[j][y]);

            int res = 0;
            for(int i = 1;i<=n;i++)
            {
                for(int j = 1;j<i;j++)
                {
                    res += f[i][j];

                }
            }
            ans = min(ans,res);
        }
    }
    cout<<ans<<endl;
    return 0;
}