// https://raw.githubusercontent.com/jaehyunp/stanfordacm
#include <bits/stdc++.h>
#define SZ(a) ((int) (a).size())

using namespace std;

typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<int> VI;

const double EPS = 1e-9;

struct LPSolver {
    int m, n;
    VI B, N;
    VVD D;

    LPSolver(const VVD &A, const VD &b, const VD &c) :
            m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, VD(n + 2)) {
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
        for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
        for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
        N[n] = -1; D[m + 1][n] = 1;
    }

    void Pivot(int r, int s) {
        double inv = 1.0 / D[r][s];
        for (int i = 0; i < m + 2; i++) if (i != r)
                for (int j = 0; j < n + 2; j++) if (j != s)
                        D[i][j] -= D[r][j] * D[i][s] * inv;
        for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] *= inv;
        for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] *= -inv;
        D[r][s] = inv;
        swap(B[r], N[s]);
    }

    bool Simplex(int phase) {
        int x = phase == 1 ? m + 1 : m;
        while (true) {
            int s = -1;
            for (int j = 0; j <= n; j++) {
                if (phase == 2 && N[j] == -1) continue;
                if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
            }
            if (D[x][s] > -EPS) return true;
            int r = -1;
            for (int i = 0; i < m; i++) {
                if (D[i][s] < EPS) continue;
                if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
                    (D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r]) r = i;
            }
            if (r == -1) return false;
            Pivot(r, s);
        }
    }

    double Solve(VD &x) {
        int r = 0;
        for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
        if (D[r][n + 1] < -EPS) {
            Pivot(r, n);
            if (!Simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<double>::infinity();
            for (int i = 0; i < m; i++) if (B[i] == -1) {
                    int s = -1;
                    for (int j = 0; j <= n; j++)
                        if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
                    Pivot(i, s);
                }
        }
        if (!Simplex(2)) return numeric_limits<double>::infinity();
        x = VD(n);
        for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
        return D[m][n + 1];
    }
};

int main() {
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;

    vector<vector<double>> a(m + 2 * (n - 2), vector<double>(m));
    vector<double> b(m + 2 * (n - 2), 0);
    vector<double> c(m, 1.0);

    vector<int> flowVariables;
    for (int i = 0; i < m; i += 1) {
        int x, y, cap;
        cin >> x >> y >> cap;
        b[i] = cap;
        a[i][i] = 1;
        if (x != 1 and x != n) {
            a[m + 2 * (x - 2)][i] = 1;
            a[m + 2 * (x - 2) + 1][i] = -1;
        } else if (x == 1) {
            flowVariables.emplace_back(i);
        }
        if (y != 1 and y != n) {
            a[m + 2 * (y - 2)][i] = -1;
            a[m + 2 * (y - 2) + 1][i] = 1;
        }
    }

    LPSolver solver(a, b, c);
    vector<double> variables;
    solver.Solve(variables);

    int flow = 0;
    for (const int& y : flowVariables) {
        flow += int(variables[y] + 1e-6);
    }
    cout << flow << '\n';

    return 0;
}