#include <bits/stdc++.h>
using namespace std;
template <class T>
using vv = vector<vector<T>>;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &t) {
  os << "{";
  for (int(i) = 0; (i) < (t.size()); ++(i)) {
    os << t[i] << ",";
  }
  os << "}" << endl;
  return os;
}
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &t) {
  return os << "(" << t.first << "," << t.second << ")";
}
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
vector<string> s_p_l_i_t(const string &s, char c) {
  vector<string> v;
  int d = 0, f = 0;
  string t;
  for (char c : s) {
    if (!d && c == ',')
      v.push_back(t), t = "";
    else
      t += c;
    if (c == '\"' || c == '\'') f ^= 1;
    if (!f && c == '(') ++d;
    if (!f && c == ')') --d;
  }
  v.push_back(t);
  return move(v);
}
void e_r_r(vector<string>::iterator it) {}
template <typename T, typename... Args>
void e_r_r(vector<string>::iterator it, T a, Args... args) {
  if (*it == " 1" || *it == "1")
    cerr << endl;
  else
    cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << ", ";
  e_r_r(++it, args...);
}
const long long MOD = 1e9 + 7;
struct UF {
  vector<int> data;
  UF(int size) : data(size, -1) {}
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};
template <class T>
class RMQ {
  vv<T> vals;

 public:
  inline T get(int l, int r) {
    if (l == r) return vals[0][l];
    const int d = 31 - __builtin_clz(l ^ r);
    return min(vals[d][l], vals[d][r]);
  }
  RMQ(){};
  RMQ(vector<T> &v, T e = -MOD) { init(v, e); }
  void init(vector<T> &v, T e) {
    int n = v.size();
    int d = 1, N = 2;
    while (N < n) N *= 2, ++d;
    vals.resize(d, vector<T>(N, e));
    for (int(i) = 0; (i) < (n); ++(i)) vals[0][i] = v[i];
    for (int(i) = 1; (i) < (d); ++(i))
      for (int(j) = 0; (j) < (N); ++(j)) {
        const int b = (j >> i | 1) << i;
        vals[i][j] = j >> i & 1 ? get(b, j) : get(j, b - 1);
      }
  }
};
class Lca {
 public:
  vector<int> dep, cld;
  vector<pair<int, int>> et;
  vector<int> l, r;
  vector<long long> wdep;
  vector<int> par;
  int weighted;
  vv<int> wei;
  RMQ<pair<int, int>> rmq;
  void dfs(const vv<int> &g, int root) {
    int n = g.size();
    vector<int> vst(n);
    stack<int> st;
    st.push(root);
    while (!st.empty()) {
      int v = st.top();
      st.pop();
      if (vst[v] == 1) {
        vst[v] = 2;
        r[v] = et.size() - 1;
        for (int(i) = 0; (i) < (g[v].size()); ++(i))
          if (g[v][i] != par[v]) cld[v] += cld[g[v][i]] + 1;
        if (par[v] >= 0) et.emplace_back(dep[par[v]], par[v]);
      } else if (vst[v] == 0) {
        st.push(v);
        vst[v] = 1;
        l[v] = et.size();
        et.emplace_back(dep[v], v);
        for (int(i) = 0; (i) < (g[v].size()); ++(i))
          if (!vst[g[v][i]]) {
            dep[g[v][i]] = dep[v] + 1;
            wdep[g[v][i]] = wdep[v] + (weighted ? wei[v][i] : 1);
            par[g[v][i]] = v;
            st.push(g[v][i]);
          }
      }
    }
  }
  Lca(const vv<int> &g) : weighted(0) {
    int n = g.size();
    par.resize(n);
    dep.resize(n);
    wdep.resize(n);
    cld.resize(n);
    l.resize(n);
    r.resize(n);
    dfs(g, 0);
    rmq.init(et, pair<int, int>(MOD, 0));
  }
  Lca(const vv<pair<int, int>> &h) : weighted(1) {
    int n = h.size();
    vv<int> g(n);
    wei.resize(n);
    for (int(i) = 0; (i) < (n); ++(i))
      for (pair<int, int> x : h[i]) {
        g[i].push_back(x.first);
        wei[i].push_back(x.second);
      }
    par.resize(n);
    dep.resize(n);
    wdep.resize(n);
    cld.resize(n);
    l.resize(n);
    r.resize(n);
    dfs(g, 0);
    rmq.init(et, pair<int, int>(MOD, 0));
  }
  int LCA(int v, int w) {
    v = l[v];
    w = l[w];
    if (v > w) swap(v, w);
    return rmq.get(v, w).second;
  }
  long long dist(int v, int w) {
    return wdep[v] + wdep[w] - 2 * wdep[LCA(v, w)];
  }
};
using namespace chrono;
system_clock::time_point starttime = system_clock::now();
int main() {
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(0);
  srand(time(0));
  int n, m;
  cin >> n >> m;
  vv<pair<int, int>> g(n);
  vector<tuple<int, int, int>> es;
  for (int(i) = 0; (i) < (m); ++(i)) {
    int x, y, c;
    cin >> x >> y >> c;
    --x;
    --y;
    g[x].emplace_back(y, c);
    g[y].emplace_back(x, c);
    es.emplace_back(c, x, y);
  }
  sort((es).rbegin(), (es).rend());
  long long mn = 1e18;
  while (
      (duration_cast<milliseconds>(system_clock::now() - starttime).count()) <
      3900) {
    long long re = 0;
    vector<tuple<int, int, int>> rm;
    vv<int> h(n);
    {
      UF uf(n);
      for (auto tp : es) {
        int c, x, y;
        tie(c, x, y) = tp;
        if (uf.unite(x, y)) {
          h[x].push_back(y);
          h[y].push_back(x);
        } else {
          re += c;
          rm.push_back(tp);
        }
      }
    }
    Lca D(h);
    int d = D.dist(0, n - 1);
    vector<int> on;
    for (int(i) = 0; (i) < (n); ++(i))
      if (D.dist(0, i) + D.dist(i, n - 1) == d) on.push_back(i);
    {
      UF uf(n);
      for (int(v) = 0; (v) < (n); ++(v))
        for (int e : h[v])
          if (D.dist(0, e) + D.dist(e, n - 1) != d ||
              D.dist(0, v) + D.dist(v, n - 1) != d)
            uf.unite(v, e);
      for (auto tp : rm) {
        int c, x, y;
        tie(c, x, y) = tp;
        int f = 0;
        for (int v : on)
          for (int w : on)
            if (uf.findSet(v, x) && uf.findSet(w, y)) f = 1;
        if (!f || uf.findSet(x, y)) re -= c;
      }
    }
    if (re == 0) {
      for (auto tp : rm) {
        int c, x, y;
        tie(c, x, y) = tp;
        {
          vector<string> a_r_g_s = s_p_l_i_t("c, x, y, 1", ',');
          e_r_r(a_r_g_s.begin(), c, x, y, 1);
        };
      }
      {
        vector<string> a_r_g_s = s_p_l_i_t("on, 1", ',');
        e_r_r(a_r_g_s.begin(), on, 1);
      };
    }
    MN(mn, re);
    random_shuffle((es).begin(), (es).end());
  }
  cout << mn << endl;
  return 0;
}
