#include <bits/stdc++.h>
const long long maxn = 16;
const long long INF = 1e15;
long long mat[maxn][maxn];
long long use[maxn][maxn];
long long backup[maxn][maxn];
long long cost[maxn][maxn];
long long par[maxn];
long long v, e;
long long res = 1e18;
void solve() {
  for (long long i = 0; i < v; i++) {
    for (long long j = 0; j < v; j++) {
      cost[i][j] = backup[i][j];
      if (use[i][j]) {
        cost[i][j] = INF;
      }
    }
  }
  long long curr = 0;
  while (true) {
    std::fill(par, par + v, -1);
    std::priority_queue<std::vector<long long>> q;
    q.push({INF, 0, -2});
    while (!q.empty()) {
      long long dist = q.top()[0];
      long long parent = q.top()[2];
      long long fr = q.top()[1];
      q.pop();
      if ((fr == v - 1 and dist >= 1e9) or par[fr] != -1) {
        continue;
      }
      par[fr] = parent;
      for (long long i = 0; i < v; i++) {
        long long next = i;
        if (par[next] == -1 and cost[fr][next] > 0) {
          q.push({std::min(cost[fr][next], dist), next, fr});
        }
      }
    }
    if (par[v - 1] != -1) {
      long long pos = v - 1;
      long long bottleneck = INF;
      while (pos != 0) {
        bottleneck = std::min(bottleneck, cost[par[pos]][pos]);
        pos = par[pos];
      }
      pos = v - 1;
      while (pos != 0) {
        cost[par[pos]][pos] -= bottleneck;
        cost[pos][par[pos]] += bottleneck;
        pos = par[pos];
      }
      curr += bottleneck;
    } else {
      break;
    }
  }
  res = std::min(res, curr);
}
void dfs(long long pos, long long bit) {
  if (pos == v - 1) {
    solve();
    return;
  }
  for (long long i = 0; i < v; i++) {
    if (!((1 << i) & bit) and mat[pos][i]) {
      use[i][pos] = true;
      use[pos][i] = true;
      dfs(i, (1 << i) | bit);
      use[i][pos] = false;
      use[pos][i] = false;
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin >> v >> e;
  for (long long i = 0; i < e; i++) {
    long long f, s;
    std::cin >> f >> s;
    f--, s--;
    std::cin >> cost[f][s];
    cost[s][f] = cost[f][s];
    mat[f][s] = mat[s][f] = true;
  }
  for (long long i = 0; i < v; i++) {
    for (long long j = 0; j < v; j++) {
      backup[i][j] = cost[i][j];
    }
  }
  dfs(0, 1);
  std::cout << res << '\n';
}
