/*
做法：
1、求最小生成树，统计标记每条边是树边还是非树边；同时把最小生成树建出来。O(mlogm)
2、预处理任意两点间的边权最大值dist[a][b]。 O(n^2)
3、依次枚举所有非树边，求min{sum + w - dist[a][b]}，满足w>dist[a][b]。O(m)
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510 , M = 10010;

struct Edge{
    int a , b , c;
    bool f;//用来记录是否是树边
    bool operator < (const Edge &W) const{
        return c < W.c;
    }
}edge[M];

int e[2 * N] , ne[2 * N] , w[2 * N] , h[N] , idx;
int dist1[N][N] , dist2[N][N];
int n , m;
int f[N];

void add(int a , int b , int c)
{
    e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}

int find(int x)
{
    return f[x] = (f[x] == x ? x : find(f[x]));
}

//为了避免死循环，记录一个父节点，使得dfs不会往父节点搜
void dfs(int u , int fa , int maxd1 , int maxd2 , int d1[] , int d2[])
{
    d1[u] = maxd1 , d2[u] = maxd2;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        if(j != fa)
        {
            int t1 = maxd1 , t2 = maxd2;//因为要搜所有的子节点,所以maxd1和maxd2不能变
            if(w[i] > t1) t2 = t1 , t1 = w[i];
            else if(w[i] < t1 && w[i] > t2) t2 = w[i];//同时求出严格次大边
            dfs(j , u , t1 , t2 , d1 , d2);
        }
    }
}

int main()
{
    int n , m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)   f[i] = i;
    memset(h , -1 , sizeof h);

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

    sort(edge , edge + m);

    //先用Kruskal求最小生成树，并建树
    long long sum = 0;
    for(int i = 0 ; i < m ; i++)
    {
        auto e = edge[i];
        int a = e.a , b = e.b , w = e.c;
        int fa = find(a) , fb = find(b);
        if(fa != fb)
        {
            f[fa] = fb;
            sum += w;
            edge[i].f = true;
            add(a , b , w) , add(b , a , w);
        }
    }

    //找出任意两点间的最大和次大树边长
    for(int i = 1 ; i <= n ; i++) dfs(i , -1 , 0 , 0 , dist1[i] , dist2[i]);

    //从小到大枚举一条非树边，求出在每一种情况下树的最小值
    long long res = 1e18;
    for(int i = 0 ; i < m ; i++)
        if(!edge[i].f)
        {
            int t;
            int a = edge[i].a , b = edge[i].b , c = edge[i].c;
            if(c > dist1[a][b]) t = dist1[a][b];//如果该边大于a、b间的最大树边，直接替换
            else if(c > dist2[a][b]) t = dist2[a][b];//如果不大于最大树边，但是大于严格的次大边，也可以直接替换
            res = min(res , sum - t + c);
        }

    cout << res << endl;
    return 0;
}