ditch

/*
ID: kh787591
LANG: JAVA
TASK: ditch
*/

import java.io.*;
import java.util.*;

class ditch
{

    static final int MAXN = 800 + 5;
    static final int MAXM = 2900 + 5;
    final static int INF = 100000008;
    public static void main(String...args)throws Exception{

        BufferedReader bf = new BufferedReader(new FileReader("ditch.in"));
        PrintWriter pw = new PrintWriter(new File("ditch.out"));

        StringTokenizer st = new StringTokenizer(bf.readLine());

        int ditches = Integer.parseInt(st.nextToken());
        int sink = Integer.parseInt(st.nextToken());
        init(sink);

        for(int i = 0; i < ditches; ++i) {
            st = new StringTokenizer(bf.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adde(r,c, Integer.parseInt(st.nextToken()));
            adde(c, r, 0);
        }
        int totalFlow = 0;

        PriorityQueue<point> pQ = new PriorityQueue<>();
        boolean [] inQ = new boolean[sink+3];
        int[] dist = new int[sink+3];
        int[] father = new int[sink+3];
        System.out.println(1);
        while(dist[sink] != INF){

            for(int i = 0; i <= sink; ++i){
                dist[i] = INF;
                father[i] = -1;
            }

            pQ = new PriorityQueue<>();
            inQ = new boolean[sink+3];
            dist[1] = 0;
            pQ.add(new point(1, 0));
            inQ[1] = true;
            int smallest = INF;

            while(!pQ.isEmpty()){

                point cur = pQ.remove();
                inQ[cur.ID] = false;
                if(cur.dist != dist[cur.ID]){
                    continue;
                }
                if(cur.ID == sink){
                    break;
                }
                for (int k = last[cur.ID]; k != -1; k = e[k].next)
                {
                    edge c = e[k];
                    if(c.c <= 0){
                        continue;
                    }
                    int m = dist[c.v];
                    //dist[c.v] = Math.min(dist[c.v], dist[c.u] + c.c);
                    if(dist[c.v] > dist[c.u] + c.c){
                        dist[c.v] = dist[c.u] + c.c;
                        if(m != dist[c.v]){
                            father[c.v] = k;

                        }


                        pQ.add(new point(c.v, dist[c.v]));
                    }


                }


            }
            if(dist[sink] == INF){
                break;
            }
            int s = sink;
            while(father[s] != -1){
                smallest = Math.min(smallest, e[father[s]].c);
                s = e[father[s]].u;
            }
            totalFlow += smallest;
            s = sink;
            while(father[s] != -1){
                e[father[s]].c -= smallest;
                e[father[s]^1].c += smallest;
                s = e[father[s]].u;
            }
        }
        pw.println(totalFlow);
        pw.close();


    }
    static class edge
    {
        public int u, v, c, next;

        edge(int _u, int _v, int _c, int _next)
        {
            u = _u; v = _v; c = _c; next = _next;
        }
    }

    static edge[] e;
    static int N, tot, last[];

    public static void init(int points)
    {
        N = points;
        tot = 0;

        e = new edge[MAXM];
        last = new int[MAXN];

        for (int i = 0; i < points; ++i)
            last[i] = -1;
        for(int i = 0; i < e.length; ++i){
            e[i] = new edge(0,0,0, 0);
        }
    }

    public static void adde(int u, int v, int c)
    {
        e[tot].u = u; e[tot].v = v; e[tot].c = c; e[tot].next = last[u]; last[u] = tot++;
    }

    public static void adde2(int u, int v, int c)
    {
        adde(u, v, c);
        adde(v, u, c);
    }
    static class point implements Comparable<point>{
        int ID;
        int dist;
        public point(int i, int j){
            ID = i;
            dist = j;
        }
        public int compareTo(point x){
            return dist - x.dist;
        }
    }

}