#include <bits/stdc++.h>

using namespace std;

template <class T>
class MaxFlow {
  public:
    MaxFlow(int _N, int _src, int _dest): src(_src), dest(_dest) { setN(_N); }
    void setN(int _N) { N = _N, graph.resize(N), index.resize(N); }
    void setSrc(int _src) { src = _src; }
    void setDest(int _dest) {dest = _dest; }
    int getN() { return N; }
    int getSrc() { return src; }
    int getDest() { return dest; }

    void addEdge(int from, int to, T forwardCap, T backwardCap = 0) {
        //assert(0 <= from && from < N && 0 <= to && to < N);
        edges.emplace_back(from, to, 0, forwardCap);
        edges.emplace_back(to, from, 0, backwardCap);
        graph[from].push_back(edges.size() - 2);
        graph[to].push_back(edges.size() - 1);
    }
    void clear() { edges.clear(), graph.clear(); }
    void reset() { for (auto &edg: edges) edg.flow = 0; }

    T maxflow() {
        return dinic();
    }
    vector <int> minCut() {
        vector <int> cut;
        for (int i = 0; i < N; ++i)
            if (dist[i] > 0)
                cut.push_back(i);
        return cut;
    }

  private:
    static const T EPS = (T) 1E-9;

    struct Edge {
        int from, to;
        T flow, cap;
        Edge(int _from = 0, int _to = 0, T _flow = 0, T _cap = 0):
            from(_from), to(_to), flow(_flow), cap(_cap) {}
        int other(int node) { return from ^ to ^ node; }
    };
    int N, src, dest;
    vector <Edge> edges;
    vector <vector <int> > graph;
    vector <int> index, dist;

    bool bfs() {
        dist.clear(), dist.resize(N, 0);
        dist[src] = 1;
        queue <int> q;
        q.push(src);
        while (!q.empty()) {
            const int node = q.front(); q.pop();
            for (const auto edg: graph[node]) {
                const int son = edges[edg].other(node);
                if (!dist[son] && edges[edg].cap - edges[edg].flow > EPS) {
                    dist[son] = 1 + dist[node];
                    q.push(son);
                }
            }
        }
        return dist[dest] > 0;
    }
    T dfs(int node, T flowToPush) {
        if (node == dest)
            return flowToPush;
        T res = 0;
        while (index[node] < (int)graph[node].size()) {
            const int edg = graph[node][index[node]];
            const int son = edges[edg].other(node);
            if (dist[son] == 1 + dist[node] && edges[edg].cap - edges[edg].flow > 0) {
                T pushed = dfs(son, min(flowToPush - res, edges[edg].cap - edges[edg].flow));
                if (pushed > EPS) {
                    edges[edg].flow += pushed;
                    edges[edg ^ 1].flow -= pushed;
                    res += pushed;
                    if (flowToPush - res <= EPS)
                        break;
                }
            }
            ++index[node];
        }
        return res;
    }
    T dinic() {
        T flow = 0;
        while (bfs()) {
            for (int i = 0; i < N; ++i)
                index[i] = 0;
            while (1) {
                T pushed = dfs(src, numeric_limits <T> :: max());
                if (pushed > EPS)
                    flow += pushed;
                else
                    break;
            }
        }
        return flow;
    }
};

int main() {
    int N = 0, M = 0;
    cin >> N >> M;
    MaxFlow <int> mf(N, 0, N - 1); // mf(N, src, dest)
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c; --a, --b;
        mf.addEdge(a, b, c);
    }
    cout << mf.maxflow() << endl;
    return 0;
}


// String Hasher
template <int B, int MOD>
struct Hasher {
    // Static hash function
    template <typename iter_type>
    static int hash(iter_type begin, iter_type end) {
        int h = 0;
        for (iter_type it = begin; it != end; ++it)
            h = (1LL * h * B + *it) % MOD;
        return h;
    }
    // Data members
    vector <int> pows, h;
    // Constructor
    template <typename iter_type>
    Hasher(iter_type begin, iter_type end) {
        const int sz = end - begin + 1;
        pows.resize(sz), h.resize(sz);
        pows[0] = 1, h[0] = 0;
        for (iter_type it = begin; it != end; ++it) {
            pows[it - begin + 1] = (1LL * pows[it - begin] * B) % MOD;
            h[it - begin + 1] = (1LL * h[it - begin] * B + (*it)) % MOD;
        }
    }
    // Continuous subsequence hash query[l, r]
    int hash(const int l, const int r) {
        int res = (h[r + 1] - 1LL * h[l] * pows[r - l + 1]) % MOD;
        if (res < 0)
            res += MOD;
        return res;
    }
};

typedef Hasher <263, 1000000000 + 7> H1;
typedef Hasher <277, 1000000000 + 9> H2;


class InputReader {
  public:
    InputReader() {
        in = stdin;
        cursor = 0;
        fread(buffer, 1, SIZE, in);
    }
    InputReader(const char *input_file) {
        in = fopen(input_file, "r");
        cursor = 0;
        fread(buffer, 1, SIZE, in);
    }
    template <typename T>
    InputReader& operator>>(T &nr) {
        while (!isdigit(buffer[cursor]))
            advance();
        nr = 0;
        while (isdigit(buffer[cursor])) {
            nr *= 10;
            nr += buffer[cursor] - '0';
            advance();
        }
        return (*this);
    }
  private:
    FILE *in;
    static const int SIZE = (1 << 17);
    char buffer[SIZE];
    int cursor;
    void advance() {
        ++ cursor;
        if (cursor == SIZE) {
            cursor = 0;
            fread(buffer, 1, SIZE, in);
        }
    }
};
 
class OutputWriter {
  public:
    OutputWriter() {
        out = stdout;
        cursor = 0;
    }
    OutputWriter(const char *output_file) {
        out = fopen(output_file, "w");
        cursor = 0;
    }
    ~OutputWriter() { flush(); }
    OutputWriter& operator<<(int nr) {
        char digits[10];
        int cnt = 0;
        do {
            digits[cnt ++] = (nr % 10 + '0');
            nr /= 10;
        } while (nr);
        for (int i = cnt - 1; i >= 0; -- i)
            (*this) << digits[i];
        return (*this);
    }
    OutputWriter& operator<<(const char &ch) {
        if (cursor == SIZE)
            flush();
        buffer[cursor ++] = ch;
        return (*this);
    }
    void flush() {
        fwrite(buffer, 1, cursor, out);
        cursor = 0;
    }
  private:
    FILE *out;
    static const int SIZE = (1 << 17);
    char buffer[SIZE];
    int cursor;
};

// String Hasher
template <int B, int MOD>
struct Hasher {
    // Static array of powers of B
    static vector <int> pows;
    static void reserve(int newSz) {
        if (newSz > (int)pows.size()) {
            const int oldSz = pows.size();
            pows.reserve(newSz);
            for (int i = oldSz; i < newSz; ++i)
                pows[i] = ((1LL * B * pows[i - 1]) % MOD);
        }
    }
    static int getPow(int pw) {
        while (pw >= (int)pows.size())
            reserve(2 * pows.size());
        return pows[pw];
    }

    // Data members
    int h, sz;
    // Constructors
    Hasher(): h(0), sz(0) {}
    Hasher(int ch): h(ch), sz(1) {}
    Hasher(int _h, int _sz): h(_h), sz(_sz) {}

    // Pushes
    void push_back(int ch) { h = (1LL * h * B + ch) % MOD, ++sz; }
    void push_front(int ch) { h = (1LL * ch * getPow(sz) + h) % MOD, ++sz; }
    // Pops
    void pop_back(int ch) {
        --sz;
        h = (h - ch) % MOD;
        if (h < 0) h += MOD;
    }
    void pop_front(int ch) {
        --sz;
        h = (h - 1LL * getPow(sz) * ch) % MOD;
        if (h < 0) h += MOD;
    }
    // Push-pop
    void push_back_pop_front(int pushCh, int popCh) {
        h = ((h - 1LL * getPow(sz - 1) * popCh) * B + pushCh) % MOD;
        if (h < 0) h += MOD;
    }
    // Concatenation
    friend Hasher operator+(const Hasher &a, const Hasher &b) { return Hasher((1LL * a.h * getPow(b.sz) + b.h) % MOD, a.sz + b.sz); }
    // Comparison
    friend bool operator==(const Hasher &a, const Hasher &b) { return make_pair(a.h, a.sz) == make_pair(b.h, b.sz); }
};
template <int B, int MOD>
vector <int> Hasher <B, MOD> :: pows = {1};

typedef Hasher <263, 1000000000 + 7> H1;
typedef Hasher <277, 1000000000 + 9> H2;

/*
	You can give a hint towards the largest string that will be represented via:
	
	H1 :: reserve(MAX_STRING_SIZE);
	...
	
	This acts like an std::vector, meaning that if the hint is not accurate, size doubling will
	occur until the string at hand can safely be represented.
*/

template <int NMAX, int MMAX>
class MaxFlowMinCost {
public:
    MaxFlowMinCost() { m = 0; }
 
    inline void setN(int _n) { n = _n; }
    inline void setS(int _s) { s = _s; }
    inline void setT(int _t) { t = _t; }
 
    inline int getN() { return n; }
    inline int getS() { return s; }
    inline int getT() { return t; }
 
    void clear() {
        m = 0;
        for (int i = 1; i <= n; ++ i)
            graph[i].clear();
    }
 
    void reset() {
        for (int i = 0; i < m; ++ i)
            edges[i].flow = 0;
    }
 
    void addEdge(int from, int to, int cap, int cost) {
        edges[m ++] = Edge(from, to, 0, cap, cost);
        edges[m ++] = Edge(to, from, 0, 0, -cost);
 
        graph[from].push_back(m - 2);
        graph[to].push_back(m - 1);
    }
 
    inline pair <int, int> computeFlow() {
        return JohnsonDinic();
    }
private:
    struct Edge {
        int from, to;
        int flow, cap, cost;
 
        Edge(int _from = 0, int _to = 0, int _flow = 0, int _cap = 0, int _cost = 0):
            from(_from), to(_to), flow(_flow), cap(_cap), cost(_cost) {}
        inline int other(int node) {
            return from ^ to ^ node;
        }
    };
 
    int n, m, s, t;
 
    vector <int> graph[NMAX];
    Edge edges[2 * MMAX];
 
    const int INF = 1e9 + 15;
 
    int dist[NMAX];
    int father[NMAX];
    bool vis[NMAX];
    int potentials[NMAX];
    priority_queue <pair <int, int> > _queue;
 
    bool Dijkstra() {
        memset(vis, 0, (n + 1) * sizeof(bool));
        for (int i = 1; i <= n; ++ i)
            dist[i] = INF;
 
        dist[s] = 0;
        _queue.push(make_pair(0, s));
 
        int node;
        while (!_queue.empty()) {
            node = _queue.top().second;
            _queue.pop();
 
            if (vis[node])
                continue;
            vis[node] = true;
 
            for (auto edge: graph[node]) {
                int other = edges[edge].other(node);
                int cost = edges[edge].cost + potentials[node] - potentials[other];
 
                if (edges[edge].flow < edges[edge].cap && dist[node] + cost < dist[other]) {
                    dist[other] = dist[node] + cost;
                    father[other] = edge;
                    _queue.push(make_pair(-dist[other], other));
                }
            }
        }
 
        for (int i = 1; i <= n; ++ i)
            dist[i] += (potentials[i] - potentials[s]);
 
        return vis[t];
    }
 
    pair <int, int> JohnsonDinic() {
        memset(potentials, 0, (n + 1) * sizeof(int));
        Dijkstra();
 
        int flow = 0, cost = 0;
        while (Dijkstra()) {
            int node = t;
            int minimum = INF;
            int sum = 0;
 
            while (node != s) {
                minimum = min(minimum, edges[father[node]].cap - edges[father[node]].flow);
                sum += edges[father[node]].cost;
                node = edges[father[node]].other(node);
            }
 
            node = t;
            while (node != s) {
                edges[father[node]].flow += minimum;
                edges[father[node] ^ 1].flow -= minimum;
                node = edges[father[node]].other(node);
            }
 
            flow += minimum;
            cost += minimum * sum;
 
            memcpy(potentials, dist, (n + 1) * sizeof(int));
        }
 
        return make_pair(flow, cost);
    }
};
 
const int NMAX = 200 + 5;
const int MMAX = 4000 + 5;
 
MaxFlowMinCost <NMAX, MMAX> f;
 
int main()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;
 
    f.setN(n);
    f.setS(s);
    f.setT(t);
 
    while (m --) {
        int a, b, cap, cost;
        cin >> a >> b >> cap >> cost;
 
        f.addEdge(a, b, cap, cost);
    }
 
    pair <int, int> ans = f.computeFlow();
    cout << ans.first << ' ' << ans.second << '\n';
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

template <const int NMAX, const int MMAX>
class MaxFLow {
public:
    MaxFLow() { m = 0; }

    inline void setN(int _n) { n = _n; }
    inline void setS(int _s) { s = _s; }
    inline void setT(int _t) { t = _t; }

	inline int getN() { return n; }
    inline int getS() { return s; }
    inline int getT() { return t; }

    void clear() {
        m = 0;
        for (int i = 1; i <= n; ++ i)
            graph[i].clear();
    }

    void reset() {
        for (int i = 0; i < m; ++ i)
            edges[i].flow = 0;
    }

    void addEdge(int from, int to, int cap) {
        edges[m ++] = Edge(from, to, 0, cap);
        edges[m ++] = Edge(to, from, 0, 0);

        graph[from].push_back(m - 2);
        graph[to].push_back(m - 1);
    }

    inline int computeFlow() {
        return Dinic();
    }

private:
    struct Edge {
        int from, to;
        int flow, cap;

        Edge(int _from = 0, int _to = 0, int _flow = 0, int _cap = 0):
            from(_from), to(_to), flow(_flow), cap(_cap) {}
        inline int other(int node) {
            return from ^ to ^ node;
        }
    };

    int n, m, s, t;

    vector <int> graph[NMAX];
    Edge edges[2 * MMAX];

    int father[NMAX];
    bool vis[NMAX];
    queue <int> _queue;

    bool bfs() {
        memset(vis, 0, (n + 1) * sizeof(bool));

        vis[s] = true;
        _queue.push(s);

        int node;
        while (!_queue.empty()) {
            node = _queue.front();
            _queue.pop();
			
			if (node == t)
				continue;

            for (auto it: graph[node])
                if (!vis[edges[it].other(node)] && edges[it].flow < edges[it].cap) {
                    father[edges[it].other(node)] = it;
                    vis[edges[it].other(node)] = true;
                    _queue.push(edges[it].other(node));
                }
        }

        return vis[t];
    }

    int Dinic() {
        int flow = 0;
        while (bfs()) {
            for (auto it: graph[t])
                if (vis[edges[it ^ 1].other(t)] && edges[it ^ 1].flow < edges[it ^ 1].cap) {
                    int node = edges[it ^ 1].other(t);
                    int minimum = edges[it ^ 1].cap - edges[it ^ 1].flow;

                    while (node != s) {
                        minimum = min(minimum, edges[father[node]].cap - edges[father[node]].flow);
                        node = edges[father[node]].other(node);
                    }

                    node = edges[it ^ 1].other(t);
                    edges[it ^ 1].flow += minimum;
                    edges[it].flow -= minimum;
                    flow += minimum;

                    while (node != s) {
                        edges[father[node]].flow += minimum;
                        edges[father[node] ^ 1].flow -= minimum;

                        node = edges[father[node]].other(node);
                    }
                }
        }

        return flow;
    }
};

const int NMAX = 1000 + 5;
const int MMAX = 5000 + 5;
MaxFLow <NMAX, MMAX> f;

int main()
{
    int n, m;
    cin >> n >> m;

    f.setN(n);
    f.setS(1);
    f.setT(n);

    int a, b, c;
    while (m --) {
        cin >> a >> b >> c;
        f.addEdge(a, b, c);
    }

    cout << f.computeFlow() << '\n';
    return 0;
}