#include<fstream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const char iname[]="traseu.in";
const char oname[]="traseu.out";
const int maxn=70;
const int INF=0x3f3f3f3f;

ifstream f(iname);
ofstream g(oname);

int S,D,i,j,n,m,ok;

queue<int> Q;
vector<int> E[maxn];

int Cost[maxn][maxn],C[maxn][maxn],F[maxn][maxn],dis[maxn],igrade[maxn],ograde[maxn],from[maxn];

bool been[maxn];

int BF()
{
    //initializam distanta si coada
    memset(dis,INF,sizeof(dis));
    memset(been,false,sizeof(been));
    dis[S]=0;
    been[S]=true;
    Q.push(S);

    //Bellman-Ford

    int x;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        if(x==D)
            continue;
        been[x]=false;
        for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
            if(C[x][*it]-F[x][*it]>0&&dis[x]+Cost[x][*it]<dis[*it])
            {
                dis[*it]=dis[x]+Cost[x][*it];
                from[*it]=x;
                if(been[*it]==false)
                    been[*it]=true,Q.push(*it);
            }
    }

    //adaugam flux;

    if(dis[D]==INF)
        return -1;

    int mint=INF;
    for(int i=D;i!=S;i=from[i])
        mint=min(mint,C[from[i]][i]-F[from[i]][i]);
    for(int i=D;i!=S;i=from[i])
    {
        F[from[i]][i]+=mint;
        F[i][from[i]]-=mint;
    }

    return mint*dis[D];
}

int main()
{
    f>>n>>m;
    int price=0;

    //formez graf cu costuri
    int x,y,z;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        E[x].push_back(y);
        E[y].push_back(x);
        Cost[x][y]=z;
        Cost[y][x]=-z;
        C[x][y]=INF;
        ++igrade[y];
        ++ograde[x];
        price+=z;
    }

    //adaugam sursa si destinatie
    D=n+1;
    S=0;
    for(i=1;i<=n;++i)
        if(igrade[i]<ograde[i])
        {
            E[i].push_back(D);
            E[D].push_back(i);
            Cost[i][D]=Cost[D][i]=0;
            C[i][D]=ograde[i]-igrade[i];
        }
        else
            if(igrade[i]>ograde[i])
            {
                E[i].push_back(S);
                E[S].push_back(i);
                Cost[i][S]=Cost[S][i]=0;
                C[S][i]=igrade[i]-ograde[i];
            }

    //flux maxim - cost minim
    ok=1;
    for(;(ok=BF())>=0;)
        price+=ok;

    g<<price<<"\n";

    f.close();
    g.close();

    return 0;
}