// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int n, m;

/// --- Union Find Library {{{ ///

struct UF {
  int n;
  vector< int > par;
  UF(int n) : n(n), par(n, -1) {}
  int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
  int size(int x) { return -par[find(x)]; }
  bool same(int a, int b) { return find(a) == find(b); }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b) return;
    if(par[a] < par[b]) swap(a, b);
    par[b] += par[a];
    par[a] = b;
  }
};

/// }}}--- ///


int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> m;
  if(n == 2) {
    cout << 0 << endl;
    return 0;
  }
  int a, b, c;
  using P = tuple<int, int, int>;
  vector<P> v;
  for(int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    a--; b--;
    if(a > b) swap(a, b);
    v.emplace_back(c, a, b);
  }
  sort(rbegin(v), rend(v));

  // 0 : 0 に属する
  // 1 : N に属する
  // 2 : 0-Nの間の木に属する
  vector<int> group(n);

  ll ans = 1e18;

  group[0] = group[n-1] = 2;
  while(1) {
    int w = 1;
    while(w < n && ++group[w] == 3) group[w] = 0, w++;
    if(w >= n - 1) break;
    // dump(group);
    ll res = 0;
    UF uf(n);
    for(int i = 0; i < m; i++) {
      int a, b, c;
      tie(c, a, b) = v[i];
      if(group[a] == group[b]) {
        if(group[a] == 2) {
          res += c;
          if(!uf.same(a, b)) {
            res -= c;
            uf.unite(a, b);
          }
        }
      } else {
        if(a == 0 && group[b] == 0) continue;
        if(b == n-1 && group[a] == 1) continue;
        res += c;
      }
    }
    if(!uf.same(0, n - 1)) continue;
    ans = min(ans, res);
  }

  cout << ans << endl;
  return 0;
}

