#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
const int INF = 1e9;
int h[maxn], mem;
struct {
  int v, next, cap;
} e[maxn * maxn * maxn];
void init() {
  memset(h, -1, sizeof(h));
  mem = 0;
}
void add(int u, int v, int c) {
  e[mem].v = v;
  e[mem].cap = c;
  e[mem].next = h[u];
  h[u] = mem++;
  e[mem].v = u;
  e[mem].cap = c;
  e[mem].next = h[v];
  h[v] = mem++;
}
int dis[maxn], q[maxn], head, tail;
bool BFS(int s, int t) {
  memset(dis, 127, sizeof(dis));
  dis[s] = 0;
  head = tail = 0;
  q[tail++] = s;
  int cnt = 0;
  while (head < tail) {
    int u = q[head++];
    for (int i = h[u]; i + 1; i = e[i].next) {
      int v = e[i].v;
      if (e[i].cap && dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        q[tail++] = v;
      }
    }
  }
  return dis[t] < 10000000;
}
int DFS(int u, int t, int limit) {
  if (u == t) return limit;
  int ans = 0;
  for (int i = h[u]; i + 1; i = e[i].next) {
    int v = e[i].v;
    if (dis[v] == dis[u] + 1 && e[i].cap) {
      int tmp = DFS(v, t, min(limit - ans, e[i].cap));
      ans += tmp;
      e[i].cap -= tmp;
      e[i ^ 1].cap += tmp;
    }
  }
  if (ans == 0) dis[u] = -2;
  return ans;
}
int dinic(int s, int t) {
  int ans = 0;
  while (BFS(s, t)) {
    int tmp;
    while (tmp = DFS(s, t, INF)) ans += tmp;
  }
  return ans;
}
int vis[maxn];
void dfss(int u) {
  vis[u] = 1;
  for (int i = h[u]; i + 1; i = e[i].next) {
    int v = e[i].v;
    if (e[i].cap && vis[v] == 0) dfss(v);
  }
}
void dfst(int u) {
  vis[u] = 2;
  for (int i = h[u]; i + 1; i = e[i].next) {
    int v = e[i].next;
    if (vis[v] == 0 && e[i ^ 1].cap) dfst(v);
  }
}
int main() {
  int n, m;
  init();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    scanf("%d%d%d", &x, &y, &c);
    add(x, y, c);
  }
  int t = dinic(1, n);
  dfss(1);
  dfst(n);
  int mx = -1;
  for (int i = 1; i <= n; i++) {
    if (vis[i] != 1) continue;
    for (int j = h[i]; j + 1; j = e[j].next) {
      int v = e[j].v;
      if (e[j].cap == 0 && vis[v] == 2) {
        mx = max(mx, e[j ^ 1].cap / 2);
      }
    }
  }
  printf("%d\n", t - mx);
  return 0;
}
