#include <bits/stdc++.h>
using namespace std;
void read(int &x) {
  char ch;
  bool ok;
  for (ok = 0, ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') ok = 1;
  for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  if (ok) x = -x;
}
const int maxn = 5e4 + 10, inf = 1e9;
int f[maxn], s, t, dis[maxn], n, m, pos[20], dep[maxn], ans;
struct oo {
  int x, y, z, w[20];
};
queue<oo> q;
struct o {
  int pre[maxn], nxt[maxn], h[maxn], v[maxn], cnt;
  void add(int x, int y, int z) {
    pre[++cnt] = y, nxt[cnt] = h[x], h[x] = cnt, v[cnt] = z;
    pre[++cnt] = x, nxt[cnt] = h[y], h[y] = cnt, v[cnt] = z;
  }
  void ins(int x, int y, int z) {
    pre[++cnt] = y, nxt[cnt] = h[x], h[x] = cnt, v[cnt] = z;
    pre[++cnt] = x, nxt[cnt] = h[y], h[y] = cnt, v[cnt] = 0;
  }
} a, b;
void bfs() {
  oo b;
  b.x = 1, b.y = 1, b.z = 0, b.w[0] = 1, b.w[1] = 1;
  q.push(b);
  while (!q.empty()) {
    oo x = q.front(), y;
    q.pop();
    for (register int i = a.h[x.x]; i; i = a.nxt[i])
      if (!(x.y & (1 << (a.pre[i] - 1))) && dis[a.pre[i]] < x.z + a.v[i]) {
        dis[a.pre[i]] = x.z + a.v[i];
        y = x, y.x = a.pre[i], y.z = dis[a.pre[i]];
        y.y |= (1 << (a.pre[i] - 1)), y.w[++y.w[0]] = a.pre[i];
        q.push(y);
        if (y.x == n) memcpy(pos, y.w, sizeof pos);
      }
  }
}
bool BFS() {
  queue<int> q;
  q.push(s);
  memset(dep, 0, sizeof dep);
  dep[s] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (register int i = b.h[x]; i; i = b.nxt[i])
      if (b.v[i] && !dep[b.pre[i]]) {
        dep[b.pre[i]] = dep[x] + 1;
        q.push(b.pre[i]);
      }
  }
  return dep[t];
}
int dfs(int x, int flow) {
  if (x == t || !flow) return flow;
  int f = flow;
  for (int i = b.h[x]; i; i = b.nxt[i])
    if (dep[b.pre[i]] > dep[x] && b.v[i]) {
      int y = dfs(b.pre[i], min(f, b.v[i]));
      f -= y, b.v[i] -= y, b.v[i ^ 1] += y;
      if (!f) return flow;
    }
  if (f == flow) dep[x] = -1;
  return flow - f;
}
int main() {
  read(n), read(m);
  a.cnt = b.cnt = 1;
  for (register int i = 1, x, y, z; i <= m; i++) {
    read(x), read(y), read(z);
    a.add(x, y, z), b.ins(x, y, z), b.ins(y, x, z);
  }
  bfs();
  int now = pos[1], tot = 1;
  while (tot < pos[0]) {
    for (register int i = a.h[now]; i; i = a.nxt[i])
      if (a.pre[i] == pos[tot + 1]) {
        b.v[i] = b.v[i ^ 1] = inf;
        break;
      }
    tot++, now = pos[tot];
  }
  s = 1, t = n;
  for (; BFS(); ans += dfs(s, inf))
    ;
  printf("%d\n", ans);
}
