#include <cstdio>
const int MAX_NODE = 110, MAX_EDGE = 10010 * 2, INF = 1e9;
typedef int arrayN[MAX_NODE];
typedef int arrayE[MAX_EDGE];
int min(int a, int b) { return a < b ? a : b; }
arrayE edgeCost, edgeFlow, toNode, nextEdge;
arrayN cur, num, dis, pre, queue, head;
int n, qhead, tail;
void addEdge(int u, int v, int w)
{
static int tot = 1;
edgeCost[++tot] = w;
edgeFlow[tot] = 0;
toNode[tot] = v;
nextEdge[tot] = head[u];
head[u] = tot;
}
int ar(int s, int t) //确认流
{
int flow = INF, p;
for (p = t; p != s; p = toNode[pre[p] ^ 1])
flow = min(flow, edgeCost[pre[p]] - edgeFlow[pre[p]]);
for (p = t; p != s; p = toNode[pre[p] ^ 1])
edgeFlow[pre[p]] += flow, edgeFlow[pre[p] ^ 1] -= flow;
return flow;
}
void bfs(int s) //拓扑
{
int now, p;
queue[tail++] = s;
dis[s] = 0;
while (qhead < tail)
{
now = queue[qhead++];
for (p = head[now]; p; p = nextEdge[p])
if (toNode[p] != s && !dis[toNode[p]])
dis[toNode[p]] = dis[now] + 1, queue[tail++] = toNode[p];
}
}
int MAXflow(int s, int t)
{
bool ok;
int ans = 0, x = s, m, p, i;
bfs(t); //对网络进行拓扑
for (i = 1; i <= n; i++)
num[dis[i]]++;
for (i = 1; i <= n; i++)
cur[i] = head[i];
while (dis[s] < n)
{
ok = false;
if (x == t) //到达目的地,更新流信息
ans += ar(s, t), x = s;
for (p = cur[x]; p; p = nextEdge[p])
if (edgeCost[p] > edgeFlow[p] && dis[x] == dis[toNode[p]] + 1)
{
ok = true, cur[x] = p, pre[toNode[p]] = p, x = toNode[p];
break;
}
if (!ok) //不可以流则回退
{
m = n;
for (p = head[x]; p; p = nextEdge[p])
if (edgeCost[p] > edgeFlow[p])
m = min(m, dis[toNode[p]]);
if (--num[dis[x]] == 0)
break;
num[dis[x] = m + 1]++;
cur[x] = head[x];
if (x != s)
x = toNode[pre[x] ^ 1];
}
}
return ans;
}
int main()
{
int m, u, v, w;
scanf("%d %d", &n, &m); //n节点,m边
for (int i = 0; i < m; ++i)
{
scanf("%d %d %d", &u, &v, &w); //u,v间有可以通过w流量的边
addEdge(u, v, w); //正向边流量w
addEdge(v, u, 0); //空的反向边
addEdge(v, u, w);
addEdge(u, v, 0);
}
printf("Max flow from Node 1 to Node n:%d", MAXflow(1, n));
return 0;
}