#include <iostream>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#define E 50000

#define maxn 1005

#define INF 0x3f3f3f3f

using namespace std;

struct Edge

{

    int u,v,flow,cost,next;

}edge[E];

int tot,head[maxn],pre[maxn],dist[maxn],vis[maxn];

int n,m;

void add(int u,int v,int flow,int cost)//flow为流量  cost为费用

{

    edge[tot].u=u;

    edge[tot].v=v;

    edge[tot].flow=flow;

    edge[tot].cost=cost;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void addEdge(int u,int v,int flow,int cost){

    add(u,v,flow,cost);

    add(v,u,,-cost);

}

bool SPFA(int s,int t,int n)

{

    int v,tmp;

    queue<int> q;

    for(int i=;i<=n;i++)

       {

        pre[i]=-;

        vis[i]=;

        dist[i]=INF;

    }

    vis[s]=;

    dist[s]=;

    q.push(s);

    while(!q.empty())

       {

        tmp=q.front();

        q.pop();

        vis[tmp]=;

        for(int k=head[tmp];k!=-;k=edge[k].next)

            if(edge[k].flow){

                v=edge[k].v;

                if(dist[v]>dist[tmp]+edge[k].cost){

                    dist[v]=dist[tmp]+edge[k].cost;

                    pre[v]=k; //存储对应的边

                    if(!vis[v]){

                        vis[v]=;

                        q.push(v);

                    }

                }

            }

    }

    return dist[t]!=INF;

}

int mcmf(int s,int t,int n)

{

    int flow=INF,ans=;

    while(SPFA(s,t,n))

       {

        ans+=dist[t];

        for(int k=pre[t];k!=-;k=pre[edge[k].u])

            flow=min(flow,edge[k].flow);

        for(int k=pre[t];k!=-;k=pre[edge[k].u])

               {

            edge[k].flow-=flow;

            edge[k^].flow+=flow;

        }

    }

    return ans;

}

void init(){

    for(int i=;i<maxn;i++)

        head[i]=-;

    tot=;

}

int main()

{

    int n,m;

    scanf("%d %d",&n,&m);

    int s=,t=n+;

    init();

    for(int i=;i<m;i++){

        int u,v,c;

        scanf("%d %d %d",&u,&v,&c);

        addEdge(u,v,,c);

        addEdge(v,u,,c);

    }

    addEdge(s,,,);

    addEdge(n,t,,);

    int ans=mcmf(s,t,n+);

    printf("%d\n",ans);

    return ;

}