1 #include <iostream>
2 #include <queue>
3 #include <stack>
4 #include <cstdio>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <bitset>
9 #include <algorithm>
10 #include <cmath>
11 #include <cstring>
12 #include <cstdlib>
13 #include <string>
14 #include <sstream>
15 #include <time.h>
16 #define x first
17 #define y second
18 #define pb push_back
19 #define mp make_pair
20 #define lson l,m,rt*2
21 #define rson m+1,r,rt*2+1
22 #define mt(A,B) memset(A,B,sizeof(A))
23 using namespace std;
24 typedef long long LL;
25 const double PI = acos(-1);
26 const int N=1e3+10;
27 const LL mod=1e9+7;
28 const int inf = 0x3f3f3f3f;
29 const LL INF=0x3f3f3f3f3f3f3f3fLL;
30 struct Edge
31 {
32 int from,to,cap,flow;
33 Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}
34 };
35 struct EK
36 {
37 int n,m;
38 vector<Edge> edges;
39 vector<int> G[N];
40 int a[N],p[N];
41 void init(int n)
42 {
43 for(int i=0; i<n; i++)G[i].clear();
44 edges.clear();
45 }
46 void AddEdge(int from,int to,int cap)
47 {
48 edges.pb(Edge(from,to,cap,0));
49 edges.pb(Edge(to,from,0,0));
50 m=edges.size();
51 G[from].pb(m-2);
52 G[to].pb(m-1);
53 }
54 int Maxflow(int s,int t)
55 {
56 int flow=0;
57 while(true)
58 {
59 mt(a,0);
60 queue<int> Q;
61 Q.push(s);
62 a[s]=inf;
63 while(!Q.empty())
64 {
65 int x=Q.front();
66 Q.pop();
67 for(int i=0; i<G[x].size(); i++)
68 {
69 Edge& e =edges[G[x][i]];
70 if(!a[e.to]&&e.cap>e.flow)
71 {
72 p[e.to]=G[x][i];
73 a[e.to]=min(a[x],e.cap-e.flow);
74 Q.push(e.to);
75 }
76 }
77 if(a[t])break;
78 }
79 if(!a[t])break;
80 for(int u=t; u!=s; u=edges[p[u]].from)
81 {
82 edges[p[u]].flow+=a[t];
83 edges[p[u]^1].flow-=a[t];
84 }
85 flow+=a[t];
86 }
87 return flow;
88 }
89 };
90 int main()
91 {
92 #ifdef Local
93 freopen("data.txt","r",stdin);
94 #endif
95 ios::sync_with_stdio(false);
96 cin.tie(0);
97 int n,m,u,v,val;
98 while(cin>>n>>m)
99 {
100 struct EK ans;
101 for(int i=0; i<n; i++)
102 {
103 cin>>u>>v>>val;
104 ans.AddEdge(u,v,val);
105 }
106 cout<<ans.Maxflow(1,m)<<endl;
107 }
108
109 #ifdef Local
110 cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
111 #endif
112 }
