#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

template<typename flow_t, typename cost_t>
struct PrimalDual {
    struct Edge {
        int to; flow_t cap; cost_t cost; int rev; bool isrev;
        Edge(int to, flow_t cap, cost_t cost, int rev, bool isrev) \
            : to(to), cap(cap), cost(cost), rev(rev), isrev(isrev) { }
    };
    const cost_t INF;
    vector<vector<Edge>> graph;
    vector<cost_t> potential, min_cost;
    vector<int> prevv, preve;
    PrimalDual(int V) : INF(numeric_limits<cost_t>::max()), graph(V) { }
    void add_edge(int from, int to, flow_t cap, cost_t cost) {
        graph[from].emplace_back(Edge(to, cap, cost, graph[to].size(), false));
        graph[to].emplace_back(Edge(from, 0, -cost, graph[from].size() - 1, true));
    }
    pair<flow_t, cost_t> min_cost_flow(int s, int t, flow_t f) {
        int V = (int)graph.size();
        cost_t ret = 0;
        using Pi = pair<cost_t, int>;
        priority_queue<Pi, vector<Pi>, greater<Pi>> que;
        potential.assign(V, 0);
        preve.assign(V, -1); prevv.assign(V, -1);
        while (f > 0) {
            min_cost.assign(V, INF); min_cost[s] = 0;
            que.emplace(0, s);
            while (!que.empty()) {
                Pi p = que.top(); que.pop();
                if (min_cost[p.second] < p.first) continue;
                for (int i = 0; i < graph[p.second].size(); i++) {
                    Edge &e = graph[p.second][i];
                    cost_t nextCost = min_cost[p.second] + e.cost;
                    nextCost += potential[p.second] - potential[e.to];
                    if (e.cap > 0 && min_cost[e.to] > nextCost) {
                        min_cost[e.to] = nextCost;
                        prevv[e.to] = p.second, preve[e.to] = i;
                        que.emplace(min_cost[e.to], e.to);
                    }
                }
            }
            if (min_cost[t] == INF) return {f, ret};
            // s-t 間最短路に沿って目一杯流す
            for (int v = 0; v < V; v++) potential[v] += min_cost[v];
            flow_t addflow = f;
            for (int v = t; v != s; v = prevv[v]) {
                addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
            }
            f -= addflow;
            ret += addflow * potential[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = graph[prevv[v]][preve[v]];
                e.cap -= addflow;
                graph[v][e.rev].cap += addflow;
            }
        }
        return {f, ret};
    }
    friend ostream& operator<<(ostream& os, PrimalDual& mcf) {
        for (int i = 0; i < mcf.graph.size(); i++) {
            for (auto &e: mcf.graph[i]) if (!e.isrev) {
                auto &rev_e = mcf.graph[e.to][e.rev];
                os << i << " -> " << e.to << " (flow: " << rev_e.cap << " / ";
                os << e.cap + rev_e.cap << ", cost: " << e.cost << ")" << endl;
            }
        }
        return os;
    }
};

int main() {
    const int INF = (int)1e9 + 7;
    int V, E; cin >> V >> E;
    PrimalDual<int, int> mcf(V);
    while (E--) {
        int a, b, c; cin >> a >> b >> c;
        mcf.add_edge(a, b, c, 0);
    }
    cout << INF - mcf.min_cost_flow(0, V - 1, INF).first << endl;
    return 0;
}


Measured memory_bytes: 3152