#include <bits/stdc++.h>
#pragma 03
#pragma GCC target("avx")
#pragma GCC optimization("unroll-loops")
using namespace std;
int a[16][16], dist[16][16], n, m, ans = 0, sum = 0, d[16][16];
vector<vector<int>> adj;
void dk(int x) {
  priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
  pq.emplace(0, x);
  dist[x][x] = 0;
  while (!pq.empty()) {
    int k = pq.top().second;
    pq.pop();
    for (int i : adj[k]) {
      if (dist[x][i] > dist[x][k] + a[k][i]) {
        dist[x][i] = dist[x][k] + a[k][i];
        pq.emplace(dist[x][i], i);
      }
    }
  }
}
vector<int> luu;
void recur(int x) {
  bool c = 0;
  for (int i = 1; i < n; ++i) {
    if (i != luu.back() && d[luu.back()][i] == 0) {
      c = 1;
      d[luu.back()][i] = 1;
      d[i][luu.back()] = 1;
      sum += dist[luu.back()][i];
      luu.emplace_back(i);
      recur(x + 1);
      luu.pop_back();
      sum -= dist[luu.back()][i];
      d[luu.back()][i] = 0;
      d[i][luu.back()] = 0;
    }
  }
  if (c == 0) {
    if (a[luu.back()][n] > 0) ans = max(ans, sum + dist[luu.back()][n]);
    return;
  }
}
signed main() {
  if (fopen(""
            ".INP",
            "r")) {
    freopen(
        ""
        ".INP",
        "r", stdin);
    freopen(
        ""
        ".OUT",
        "w", stdout);
  };
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  adj.resize(n + 1);
  for (int i = 1; i < 16; ++i)
    for (int j = 1; j < 16; ++j) dist[i][j] = INT_MAX;
  int all = 0;
  for (int i = 0; i < m; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
    a[x][y] = a[y][x] = z;
    all += z;
  }
  for (int i = 1; i < n + 1; ++i) dk(i);
  luu.emplace_back(1);
  recur(0);
  cout << all - ans;
  return 0;
}
