/**************************************************************

     Problem: 1977

     User: yzcstca

     Language: C++

     Result: Accepted

     Time:2344 ms

     Memory:35048 kb

 ****************************************************************/

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<string>

 #include<map>

 #include<set>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<ctime>

 #define repf(i, a, b) for (int i = (a); i <= (b); ++i)

 #define M0(x)  memset(x, 0, sizeof(x))

 #define vii vector< pair<int, int> >::iterator

 #define x first

 #define y second

 #define two(i) (1 << i)

 using namespace std;

 typedef long long ll;

 typedef pair<int, int> pii;

 const int maxn = ;

 const int maxm = ;

 struct oo{

     int u, v, w;

     bool operator<(const oo& p) const{

         return w < p.w;

     }

 } E[maxm];

 vector<pii> e[maxn];

 int fa[maxn], intree[maxm];

 int n, m, ans;

 int dep[maxn], f[maxn][], vv[maxn][][];

 void init(){

     for (int i = ; i < m; ++i)

          scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);

     repf(i, , n) e[i].clear();

 }

 inline int find(const int& k){

     return fa[k] == k ? k : fa[k] = find(fa[k]);

 }

 int vis[maxn], t[maxn];

 void bfs(){

      M0(vis);

      queue<int> q;

      q.push(), dep[] = , vis[] = ;

      int u, v, cnt;

      t[cnt = ] = ;

      while (!q.empty()){

           u = q.front();

           q.pop();

           for (vii it = e[u].begin(); it != e[u].end(); ++it){

                   if (vis[it->x]) continue;

                   dep[it->x] = dep[u] + ;

                   f[it->x][] = u;

                   vv[it->x][][] = it->y, vv[it->x][][] = -;

                   q.push(it->x), vis[it->x] = , t[++cnt] = it->x;

           }

      }

 }

 void update(int v[],const int& val){

      if (val > v[])

           swap(v[], v[]), v[] = val;

      else if (val < v[] && val > v[])

           v[] = val;

 }

 void rmq(){

     int u, v;

     repf(i, , n){

          u = t[i];

          for (int i = ; i <= ; ++i){

               if (two(i) > dep[u]) break;

               v = f[u][i-];

               f[u][i] = f[v][i-];

               vv[u][i][] = vv[u][i][] = -;

               update(vv[u][i], vv[u][i-][]);

               update(vv[u][i], vv[u][i-][]);

               update(vv[u][i], vv[v][i-][]);

               update(vv[u][i], vv[v][i-][]);

          }

     }

 }

 int res[];

 void query(int u, int s, int res[]){

     for (int i = ; i <= ; ++i) if (s & two(i))

          update(res, vv[u][i][]), update(res, vv[u][i][]), u = f[u][i], s ^= two(i);

 }

 void work(int u, int v, const int& w){

      if (dep[u] > dep[v]) swap(u, v);

      int fu = u, fv = v, h;

      if (dep[fu] != dep[fv]){

             h = dep[fv] - dep[fu];

             for (int i = ; i <= ; ++i) if (h & two(i))

                   h ^= two(i), fv = f[fv][i];

      }

      if (fu == fv){

              res[] = res[] = -;

              query(v, dep[v] - dep[u], res);

              h = (res[] != w) ? res[] : res[];

              if (h != -) ans = min(ans, w - h);

              return;

      }

      for (int i = ; i >= ; --i){

             if (two(i) > dep[fu]) continue;

             if (f[fu][i] != f[fv][i])

                   fu = f[fu][i], fv = f[fv][i];

      }

      fu = f[fu][];

      res[] = res[] = -;

      query(u, dep[u] - dep[fu], res);

      query(v, dep[v] - dep[fu], res);

      h = (res[] != w) ? res[] : res[];

      if (h != -) ans = min(ans, w - h);

 }

 void solve(){

     repf(i, , n) fa[i] = i;

     sort(E, E + m);

     memset(intree, , sizeof(int) * (m + ));

     int u, v, fu, fv, w;

     ll mst = ;

     repf(i, , m-){

          u = E[i].u, v = E[i].v, w = E[i].w;

          fu = find(u), fv = find(v);

          if (fu != fv){

              fa[fu] = fv, intree[i] = ;

              mst += E[i].w;

              e[u].push_back(make_pair(v, w));

              e[v].push_back(make_pair(u, w) );

          }

     }

     bfs();

     rmq();

     ans = 0x3fffffff;

     for (int i = ; i < m; ++i) if (!intree[i])

          work(E[i].u, E[i].v, E[i].w);

     cout << mst + ans << endl;

 }

 int main(){

 //    freopen("a.in", "r", stdin);

 //    freopen("a.out", "w", stdout);

     while (scanf("%d%d", &n, &m) != EOF){

            init();

            solve();

     }

     return ;

 }