#include <iostream>
#include <cstring>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 200+10;
const int INF = 1e9+10;
struct Edge{
    int from, to, cap, flow;
};
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
void AddEdge(int u, int v, int cap){
    edges.push_back(Edge{u, v, cap, 0});
    edges.push_back(Edge{v, u, 0, 0});
    int m = edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn];
bool BFS(int s, int t){
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    memset(d, 0, sizeof(d));
    d[t] = 0;
    vis[t] = true;
    q.push(t);
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int i=0; i<G[temp].size(); i++){
            Edge &e = edges[G[temp][i]];
            if(!vis[e.to]&&e.cap>e.flow){
                vis[e.to] = true;
                d[e.to] = d[temp]+1;
                q.push(e.to);
            }
        }
    }
    return vis[s];
}
int p[maxn];
int num[maxn];
int cur[maxn];
int Augment(int s, int t) {
    int x = t, a = INF;
    while(x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap-e.flow);
      x = edges[p[x]].from;
    }
    x = t;
    while(x != s) {
      edges[p[x]].flow += a;
      edges[p[x]^1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
}
int Maxflow(int s, int t) {
    int flow = 0;
    BFS(s, t);
    memset(num, 0, sizeof(num));
    for(int i = 0; i < n; i++) num[d[i]]++;
    int x = s;
    memset(cur, 0, sizeof(cur));
    while(d[s] < n) {
      if(x == t) {
        flow += Augment(s, t);
        x = s;
      }
      int ok = 0;
      for(int i = cur[x]; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(e.cap > e.flow && d[x] == d[e.to] + 1) { // Advance
          ok = 1;
          p[e.to] = G[x][i];
          cur[x] = i; // 注意
          x = e.to;
          break;
        }
      }
      if(!ok) { // Retreat
        int m = n-1; // 初值注意
        for(int i = 0; i < G[x].size(); i++) {
          Edge& e = edges[G[x][i]];
          if(e.cap > e.flow) m = min(m, d[e.to]);
        }
        if(--num[d[x]] == 0) break;
        num[d[x] = m+1]++;
        cur[x] = 0; // 注意
        if(x != s) x = edges[p[x]].from;
      }
    }
    return flow;
}
void init(){
    for(int i=0; i<maxn; i++)G[i].clear();
    edges.clear();
    memset(p, 0, sizeof(p));
    memset(cur, 0, sizeof(cur));
    memset(num, 0, sizeof(num));
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>m>>n){
        init();
        int u, v, w;
        for(int i=0; i<m; i++){
            cin>>u>>v>>w;
            AddEdge(u, v, w);
        }
        int ans = Maxflow(1, n);
        cout<<ans<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
int G[maxn][maxn];
int main()
{
    freopen("out.txt", "w", stdout);
    srand((unsigned)time(NULL));
    int n = 2000;
    memset(G, -1, sizeof(G));
    int s = 1, t = n;
    for(int i=1; i<n; i++){
        int w = rand();
        G[i][i+1] = w;
    }
    for(int i=0; i<n*n/100; i++){
        int u = rand()%n+1;
        int v = rand()%n+1;
        int w = rand()%n+1;
        if(u == v) continue;
        if(G[u][v] != -1) continue;
        else{
            G[u][v] = w;
        }
    }
    int tot = 0;
    printf("%d ", n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j) continue;
            if(G[i][j] == -1) continue;
            //printf("%d %d %d\n", i, j, G[i][j]);
            tot++;
        }
    }
    printf("%d\n", tot);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j) continue;
            if(G[i][j] == -1) continue;
            printf("%d %d %d\n", i, j, G[i][j]);
        }
    }
    return 0;
}