A flow network is a directed graph which has a $source$ and a $sink$. In a flow network, each edge $(u, v)$ has a capacity $c(u, v)$. Each edge receives a flow, but the amount of flow on the edge can not exceed the corresponding capacity. Find the maximum flow from the $source$ to the $sink$.

Constraints

* $2 \leq |V| \leq 100$
* $1 \leq |E| \leq 1000$
* $0 \leq c_i \leq 10000$

Input

A flow network is given in the following format.

$|V|\;|E|$
$u_0\;v_0\;c_0$
$u_1\;v_1\;c_1$
:
$u_{|E|-1}\;v_{|E|-1}\;c_{|E|-1}$



$|V|$, $|E|$ is the number of vertices and edges of the flow network respectively. The vertices in $G$ are named with the numbers 0, 1,..., $|V|-1$. The source is 0 and the sink is $|V|-1$.

$u_i$, $v_i$, $c_i$ represent $i$-th edge of the flow network. A pair of $u_i$ and $v_i$ denotes that there is an edge from $u_i$ to $v_i$ and $c_i$ is the capacity of $i$-th edge.

Output

Print the maximum flow.

Example

Input

4 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2


Output

3
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

class MaxFlow{
    class Edge{
        int to,cap,revIndex;
        Edge(int to,int cap,int rev){
            this.to = to;
            this.cap = cap;
            revIndex = rev;
        }
    }

    List<Edge>[] edgeList;
    int N;
    int[] index;
    int[] level;


    @SuppressWarnings("unchecked")
    MaxFlow(int N){
        this.N = N;
        edgeList = new ArrayList[N];
        index = new int[N];
        level = new int[N];
        for(int i=0;i<N;++i)edgeList[i]=new ArrayList<>();
    }

    void addEdge(int from,int to,int cap){
        edgeList[from].add(new Edge(to,cap,edgeList[to].size()));
        edgeList[to].add(new Edge(from,0,edgeList[from].size()-1));
    }

    

    
    int dfs(int v,int t,int f){
        if(v==t)return f;
        for(;index[v]<edgeList[v].size();++index[v]){
            Edge e = edgeList[v].get(index[v]);
            if(e.cap<=0 || level[e.to] <= level[v])continue;
            int u = e.to;
            int F = dfs(u,t,Math.min(f,e.cap));
            if(F>0){
                e.cap -= F;
                edgeList[u].get(e.revIndex).cap += F;
                return F;
            }
        }
        return 0;
    }

    void bfs(int s){
        Arrays.fill(level,-1);
        level[s]=0;
        Deque<Integer> que = new ArrayDeque<>();
        que.add(s);
        while(!que.isEmpty()){
            int v = que.poll();
            for(Edge e : edgeList[v]){
                if(level[e.to]<0 && e.cap>0){
                    level[e.to]=level[v]+1;
                    que.add(e.to);
                }
            }
        }
    }

    int getMaxFlow(int s,int t){
        int res = 0;
        while(true){
            Arrays.fill(index,0);
            bfs(s);
            if(level[t]<0)break;
            while(true){
                int f = dfs(s,t,Integer.MAX_VALUE);
                if(f<=0)break;
                res+=f;

            }
        }
        return res;
    }
}

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        MaxFlow mf = new MaxFlow(n);
        while(m-->0){
            int from = scan.nextInt();
            int to = scan.nextInt();
            int cap = scan.nextInt();
            mf.addEdge(from, to, cap);
        }
        System.out.println(mf.getMaxFlow(0, n-1));

    }
}



class c{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int r=scan.nextInt();
        int c = scan.nextInt();
        boolean[][] C = new boolean[r][c];
        for(int i=0;i<r;++i){
            String s = scan.next();
            for(int j=0;j<c;++j){
                C[i][j] = s.charAt(j)=='.';
            }
        }


        MaxFlow mf = new MaxFlow(r*c+2);

        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        for(int i=0;i<r;++i){
            for(int j=0;j<c;++j){
                if(!C[i][j])continue;
                int from = i*c + j;
                for(int k=0;k<4;++k){
                    if(i+dy[k]<0 || i+dy[k] >=r || j+dx[k]<0 || j+dx[k]>=c || !C[i+dy[k]][j+dx[k]])continue;
                    int to = (i+dy[k])*c + j+dx[k];
                    mf.addEdge(from, to, 1);
                }
            }
        }

        int s = r*c;
        int t = r*c+1;
        int white = 0;
        for(int i=0;i<r;++i){
            for(int j=0;j<c;++j){
                if(C[i][j]){
                    ++white;
                    int to = i*c+j;
                    if((i+j)%2==0)mf.addEdge(s, to, 1);
                    else mf.addEdge(to, t, 1);
                }
            }
        }

        int maxflow = mf.getMaxFlow(s, t);

        System.out.println(white - maxflow);
    }
}
