1 /**************************************************************  2     Problem: 1977  3     User: yzcstca  4     Language: C++  5     Result: Accepted  6     Time:2344 ms  7     Memory:35048 kb  8 ****************************************************************/  9  10 #include<cstdio> 11 #include<iostream> 12 #include<cstring> 13 #include<cstdlib> 14 #include<cmath> 15 #include<algorithm> 16 #include<string> 17 #include<map> 18 #include<set> 19 #include<vector> 20 #include<queue> 21 #include<stack> 22 #include<ctime> 23 #define repf(i, a, b) for (int i = (a); i <= (b); ++i) 24 #define M0(x)  memset(x, 0, sizeof(x)) 25 #define vii vector< pair<int, int> >::iterator 26 #define x first 27 #define y second 28 #define two(i) (1 << i) 29 using namespace std; 30 typedef long long ll; 31 typedef pair<int, int> pii; 32 const int maxn = 101001; 33 const int maxm = 301000; 34 struct oo{ 35     int u, v, w; 36     bool operator<(const oo& p) const{ 37         return w < p.w; 38     } 39 } E[maxm]; 40 vector<pii> e[maxn]; 41 int fa[maxn], intree[maxm]; 42 int n, m, ans; 43 int dep[maxn], f[maxn][20], vv[maxn][20][2]; 44   45 void init(){ 46     for (int i = 0; i < m; ++i) 47          scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w); 48     repf(i, 0, n) e[i].clear(); 49 } 50   51   52 inline int find(const int& k){ 53     return fa[k] == k ? k : fa[k] = find(fa[k]); 54 } 55   56 int vis[maxn], t[maxn]; 57 void bfs(){ 58      M0(vis); 59      queue<int> q; 60      q.push(1), dep[1] = 0, vis[1] = 1; 61      int u, v, cnt; 62      t[cnt = 1] = 1; 63      while (!q.empty()){ 64           u = q.front(); 65           q.pop(); 66           for (vii it = e[u].begin(); it != e[u].end(); ++it){ 67                   if (vis[it->x]) continue; 68                   dep[it->x] = dep[u] + 1; 69                   f[it->x][0] = u; 70                   vv[it->x][0][0] = it->y, vv[it->x][0][1] = -1; 71                   q.push(it->x), vis[it->x] = 1, t[++cnt] = it->x; 72           } 73      } 74 } 75   76 void update(int v[],const int& val){ 77      if (val > v[0])  78           swap(v[0], v[1]), v[0] = val; 79      else if (val < v[0] && val > v[1]) 80           v[1] = val; 81 } 82   83 void rmq(){ 84     int u, v; 85     repf(i, 1, n){ 86          u = t[i]; 87          for (int i = 1; i <= 17; ++i){ 88               if (two(i) > dep[u]) break; 89               v = f[u][i-1]; 90               f[u][i] = f[v][i-1]; 91               vv[u][i][0] = vv[u][i][1] = -1; 92               update(vv[u][i], vv[u][i-1][0]); 93               update(vv[u][i], vv[u][i-1][1]); 94               update(vv[u][i], vv[v][i-1][0]); 95               update(vv[u][i], vv[v][i-1][1]); 96          } 97     } 98 } 99  100 int res[2];101 void query(int u, int s, int res[]){102     for (int i = 0; i <= 17; ++i) if (s & two(i))103          update(res, vv[u][i][0]), update(res, vv[u][i][1]), u = f[u][i], s ^= two(i);104 }105  106 void work(int u, int v, const int& w){107      if (dep[u] > dep[v]) swap(u, v);108      int fu = u, fv = v, h;109      if (dep[fu] != dep[fv]){110             h = dep[fv] - dep[fu];111             for (int i = 0; i <= 17; ++i) if (h & two(i))112                   h ^= two(i), fv = f[fv][i];113      }114      if (fu == fv){115              res[0] = res[1] = -1;116              query(v, dep[v] - dep[u], res);117              h = (res[0] != w) ? res[0] : res[1];118              if (h != -1) ans = min(ans, w - h);119              return;120      }121      for (int i = 17; i >= 0; --i){122             if (two(i) > dep[fu]) continue;123             if (f[fu][i] != f[fv][i])124                   fu = f[fu][i], fv = f[fv][i];125      }126      fu = f[fu][0];127      res[0] = res[1] = -1;128      query(u, dep[u] - dep[fu], res);129      query(v, dep[v] - dep[fu], res);130      h = (res[0] != w) ? res[0] : res[1];131      if (h != -1) ans = min(ans, w - h);132 }133  134 void solve(){135     repf(i, 0, n) fa[i] = i;136     sort(E, E + m);137     memset(intree, 0, sizeof(int) * (m + 10));138     int u, v, fu, fv, w;139     ll mst = 0;140     repf(i, 0, m-1){141          u = E[i].u, v = E[i].v, w = E[i].w;142          fu = find(u), fv = find(v);143          if (fu != fv){144              fa[fu] = fv, intree[i] = 1;145              mst += E[i].w;146              e[u].push_back(make_pair(v, w));147              e[v].push_back(make_pair(u, w) );148          }149     }150     bfs();151     rmq();152     ans = 0x3fffffff;153     for (int i = 0; i < m; ++i) if (!intree[i])154          work(E[i].u, E[i].v, E[i].w);155     cout << mst + ans << endl;156          157 }158  159 int main(){160 //    freopen("a.in", "r", stdin);161 //    freopen("a.out", "w", stdout);162     while (scanf("%d%d", &n, &m) != EOF){163            init();164            solve();165     }166     return 0;167 }