/*
author : [ Godsent ]
created : 2025.07.30 02:03:23
*/
#include <bits/stdc++.h>
#define el "\n"
#define int long long
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define prs(n) fixed << setprecision(n)
const int mod = 1e9 + 7;
const int N = 1e3 + 5;
const int INF = 1e18;
using namespace std;
vector<int> adj[N];
int n, m, s, t, maxFlow, minCut;
int lastVertexId[N];
int f[N][N], c[N][N], d[N];
int visited[N];
vector<int> S;
map<int,int> T;
void bfs() {
queue<int> q;
q.push(s);
fill(d, d + n + 1, INF);
d[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &v : adj[u]) {
if (d[v] != INF || c[u][v] - f[u][v] == 0) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
}
int increaseFlow(int u, int currDelta) {
if (currDelta == 0) return 0;
if (u == t) return currDelta;
for (; lastVertexId[u] < sz(adj[u]); lastVertexId[u]++) {
int v = adj[u][lastVertexId[u]];
if (d[v] != d[u] + 1 || c[u][v] - f[u][v] == 0) continue;
int delta = increaseFlow(v, min(currDelta, c[u][v] - f[u][v]));
if (delta == 0) continue;
f[u][v] += delta;
f[v][u] -= delta;
return delta;
}
return 0;
}
void dfs(int u) {
visited[u]++;
for (auto &v : adj[u]) {
if (!visited[v] && c[u][v] - f[u][v] > 0) dfs(v);
}
}
int findMinCut() {
S.pb(s);
T[t]++;
dfs(s);
for (int u = 1; u <= n; u++) {
if (visited[u]) {
for (auto &v : adj[u]) {
if (!visited[v] && c[u][v] > 0) {
minCut += c[u][v];
}
}
}
}
return minCut;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n >> m;
s = 1;
t = n;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v >> c[u][v];
adj[u].pb(v);
adj[v].pb(u);
}
while (d[t] != INF) {
bfs();
for (int i = 1; i <= n; i++) lastVertexId[i] = 0;
while (int delta = increaseFlow(s, INF)) maxFlow += delta;
}
cout << maxFlow << el;
cout << findMinCut() << el;
return 0;
}
LyoKICAgIGF1dGhvciAgOiBbIEdvZHNlbnQgXQogICAgY3JlYXRlZCA6IDIwMjUuMDcuMzAgMDI6MDM6MjMKKi8KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGVsICJcbiIKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgc3ooeCkgKChpbnQpKHgpLnNpemUoKSkKI2RlZmluZSBhbGwodikgKHYpLmJlZ2luKCksICh2KS5lbmQoKQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIHBycyhuKSBmaXhlZCA8PCBzZXRwcmVjaXNpb24obikKCmNvbnN0IGludCBtb2QgPSAxZTkgKyA3Owpjb25zdCBpbnQgTiA9IDFlMyArIDU7CmNvbnN0IGludCBJTkYgPSAxZTE4OwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjxpbnQ+IGFkaltOXTsKaW50IG4sIG0sIHMsIHQsIG1heEZsb3csIG1pbkN1dDsKaW50IGxhc3RWZXJ0ZXhJZFtOXTsKaW50IGZbTl1bTl0sIGNbTl1bTl0sIGRbTl07CmludCB2aXNpdGVkW05dOwp2ZWN0b3I8aW50PiBTOwptYXA8aW50LGludD4gVDsKCnZvaWQgYmZzKCkgewogIHF1ZXVlPGludD4gcTsKICBxLnB1c2gocyk7CiAgZmlsbChkLCBkICsgbiArIDEsIElORik7CiAgZFtzXSA9IDA7CiAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgIGludCB1ID0gcS5mcm9udCgpOwogICAgcS5wb3AoKTsKICAgIGZvciAoYXV0byAmdiA6IGFkalt1XSkgewogICAgICBpZiAoZFt2XSAhPSBJTkYgfHwgY1t1XVt2XSAtIGZbdV1bdl0gPT0gMCkgY29udGludWU7CiAgICAgIGRbdl0gPSBkW3VdICsgMTsKICAgICAgcS5wdXNoKHYpOwogICAgfQogIH0KfQoKaW50IGluY3JlYXNlRmxvdyhpbnQgdSwgaW50IGN1cnJEZWx0YSkgewogIGlmIChjdXJyRGVsdGEgPT0gMCkgcmV0dXJuIDA7CiAgaWYgKHUgPT0gdCkgcmV0dXJuIGN1cnJEZWx0YTsKCiAgZm9yICg7IGxhc3RWZXJ0ZXhJZFt1XSA8IHN6KGFkalt1XSk7IGxhc3RWZXJ0ZXhJZFt1XSsrKSB7CiAgICBpbnQgdiA9IGFkalt1XVtsYXN0VmVydGV4SWRbdV1dOwogICAgaWYgKGRbdl0gIT0gZFt1XSArIDEgfHwgY1t1XVt2XSAtIGZbdV1bdl0gPT0gMCkgY29udGludWU7CgogICAgaW50IGRlbHRhID0gaW5jcmVhc2VGbG93KHYsIG1pbihjdXJyRGVsdGEsIGNbdV1bdl0gLSBmW3VdW3ZdKSk7CiAgICBpZiAoZGVsdGEgPT0gMCkgY29udGludWU7CiAgICBmW3VdW3ZdICs9IGRlbHRhOwogICAgZlt2XVt1XSAtPSBkZWx0YTsKICAgIHJldHVybiBkZWx0YTsKICB9CiAgcmV0dXJuIDA7Cn0KCnZvaWQgZGZzKGludCB1KSB7CiAgdmlzaXRlZFt1XSsrOwogIGZvciAoYXV0byAmdiA6IGFkalt1XSkgewogICAgaWYgKCF2aXNpdGVkW3ZdICYmIGNbdV1bdl0gLSBmW3VdW3ZdID4gMCkgZGZzKHYpOwogIH0KfQoKaW50IGZpbmRNaW5DdXQoKSB7CiAgUy5wYihzKTsKICBUW3RdKys7CgogIGRmcyhzKTsKCiAgZm9yIChpbnQgdSA9IDE7IHUgPD0gbjsgdSsrKSB7CiAgICBpZiAodmlzaXRlZFt1XSkgewogICAgICBmb3IgKGF1dG8gJnYgOiBhZGpbdV0pIHsKICAgICAgICBpZiAoIXZpc2l0ZWRbdl0gJiYgY1t1XVt2XSA+IDApIHsKICAgICAgICAgIG1pbkN1dCArPSBjW3VdW3ZdOwogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KCiAgcmV0dXJuIG1pbkN1dDsKfQoKc2lnbmVkIG1haW4oKSB7CiAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgY2luLnRpZSgwKTsKICBjb3V0LnRpZSgwKTsKCiNpZm5kZWYgT05MSU5FX0pVREdFCiAgZnJlb3BlbigidGVzdC5pbnAiLCAiciIsIHN0ZGluKTsKICBmcmVvcGVuKCJ0ZXN0Lm91dCIsICJ3Iiwgc3Rkb3V0KTsKI2VuZGlmCgogIGNpbiA+PiBuID4+IG07CiAgcyA9IDE7CiAgdCA9IG47CgogIGZvciAoaW50IGkgPSAxLCB1LCB2OyBpIDw9IG07IGkrKykgewogICAgY2luID4+IHUgPj4gdiA+PiBjW3VdW3ZdOwogICAgYWRqW3VdLnBiKHYpOwogICAgYWRqW3ZdLnBiKHUpOwogIH0KCiAgd2hpbGUgKGRbdF0gIT0gSU5GKSB7CiAgICBiZnMoKTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgbGFzdFZlcnRleElkW2ldID0gMDsKICAgIHdoaWxlIChpbnQgZGVsdGEgPSBpbmNyZWFzZUZsb3cocywgSU5GKSkgbWF4RmxvdyArPSBkZWx0YTsKICB9CgogIGNvdXQgPDwgbWF4RmxvdyA8PCBlbDsKICBjb3V0IDw8IGZpbmRNaW5DdXQoKSA8PCBlbDsKCiAgcmV0dXJuIDA7Cn0K