#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxv = +;

const int maxe = +;

struct Edge

{

    int v,cap,cost,nxt;

    void IN(int V,int C,int c,int N)

    {

        v = V; cap = C; cost = c; nxt = N;

    }

}edges[maxe];

int head[maxv],ecnt,vcnt;

void AddEdge(int u,int v,int C,int c)

{

    edges[ecnt].IN(v,C,c,head[u]);

    head[u] = ecnt++;

    edges[ecnt].IN(u,,-c,head[v]);

    head[v] = ecnt++;

}

const int INF = 0x3f3f3f3f;

int S,T;

bool vis[maxv];

int d[maxv],p[maxv],a[maxv];

bool spfa()

{

    memset(d,0x3f,sizeof(int)*vcnt);

    memset(vis,,sizeof(bool)*vcnt);

    queue<int> q; q.push(S); d[S] = ;

    a[S] = INF;

    while(q.size()){

        int u = q.front(); q.pop();

        vis[u] = false;

        for(int i = head[u]; ~i; i = edges[i].nxt){

            Edge &e = edges[i];

            if(e.cap&& d[e.v] > d[u]+e.cost){

                d[e.v] = d[u] + e.cost;

                p[e.v] = i;

                a[e.v] = min(a[u],e.cap);

                if(!vis[e.v]) { q.push(e.v); vis[e.v] = true; }

            }

        }

    }

    return d[T] != INF;

}

ll MinCostMaxFlow()

{

    ll cost = ;

    while(spfa()){

        cost += d[T];

        for(int i = T; i != S; i = edges[p[i]^].v){

            edges[p[i]].cap -= a[T];

            edges[p[i]^].cap += a[T];

        }

    }

    return cost;

}

int pin[maxv],pout[maxv];

int main()

{

    //freopen("in.txt","r",stdin);

    int v,e;

    int S = ; T = ;

    while(~scanf("%d%d",&v,&e)){

        vcnt = ; ecnt = ;

        pin[] = pout[] = vcnt++;

        pin[v] = pout[v] = vcnt++;

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

            pin[i] = vcnt++;

            pout[i] = vcnt++;

        }

        memset(head,-,sizeof(int)*(vcnt));

        AddEdge(S,pin[],,);

        AddEdge(pout[v],T,,);

        for(int i = ; i < v; i++) AddEdge(pin[i],pout[i],,);

        while(e--){

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

            AddEdge(pout[u],pin[v],,c);

        }

        printf("%lld\n",MinCostMaxFlow());

    }

    return ;

}