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

#define maxN 64

#define INF 0x7fffffff

using namespace std;

ifstream in;
ofstream out;

vector <int> g[maxN];

int cost[maxN][maxN];
int cap[maxN][maxN];
int f[maxN][maxN];
int gin[maxN];
int gout[maxN];
int T[maxN];
int dist[maxN];

int flux=0;
int Source;
int Sink;

inline int bellmanford()
{
    queue <int> q;
    int use[maxN];

    memset(T,0,sizeof(T));
    memset(use,0,sizeof(use));

    for(int i=Source;i<=Sink;++i) dist[i]=INF;

    q.push(Source);
    dist[Source]=0;

    for(int nod;!q.empty();q.pop())
    {
        nod=q.front();
        use[nod]=0;

        for(vector <int>::iterator it=g[nod].begin();it!=g[nod].end();++it)
            if(cap[nod][*it]>f[nod][*it]&&dist[*it]>dist[nod]+cost[nod][*it])
            {
                T[*it]=nod;
                dist[*it]=dist[nod]+cost[nod][*it];
                if(!use[*it])
                {
                    use[*it]=1;
                    q.push(*it);
                }
            }
    }

    return T[Sink];
}

inline void flow()
{
    for(int drum=bellmanford();drum;drum=bellmanford())
    {
        int min=INF;
        for(int nod=Sink;nod!=Source;nod=T[nod])
            if(min>cap[T[nod]][nod]-f[T[nod]][nod])
                min=cap[T[nod]][nod]-f[T[nod]][nod];

        if(min<=0) continue;

        flux+=dist[Sink]*min;

        for(int nod=Sink;nod!=Source;nod=T[nod])
        {
            f[T[nod]][nod]+=min;
            f[nod][T[nod]]-=min;
        }
    }
}

int main()
{
    int M,N,x,y;

    in.open("traseu.in");

    memset(cost,0,sizeof(cost));
    memset(gin,0,sizeof(gin));
    memset(gout,0,sizeof(gout));
    memset(cap,0,sizeof(cap));

    in>>N>>M;
    for(;M--;)
    {
        in>>x>>y;
        in>>cost[x][y];
        cost[y][x]=-cost[x][y];

        ++gin[y];
        ++gout[x];

        g[x].push_back(y);
        g[y].push_back(x);

        cap[x][y]=INF;

        flux+=cost[x][y];
    }

    in.close();

    memset(f,0,sizeof(f));

    Source=0;
    Sink=N+1;

    for(int i=1;i<=N;++i)
        if(gin[i]>gout[i])
        {
            cap[Source][i]=gin[i]-gout[i];
            g[Source].push_back(i);
            g[i].push_back(Source);
        }
        else
        if(gin[i]<gout[i])
        {
            cap[i][Sink]=gout[i]-gin[i];
            g[i].push_back(Sink);
            g[Sink].push_back(i);
        }

    flow();

    out.open("traseu.out");

    out<<flux<<'\n';

    out.close();

    return 0;
}