#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int N=65,inf=1<<30;
int drum[N][N],cap[N][N],flux[N][N],cost[N][N],grad[N],T[N],dist[N],n;
struct Muchie
{
    int y,c;
};
vector<int> a[N];
vector<Muchie> b[N];
queue<int> Q;

ifstream in("traseu.in");
ofstream out("traseu.out");

inline int dif(int x,int y)
{
    return cap[x][y]-flux[x][y];
}

inline int min(int a,int b)
{
    return a<b ? a : b;
}

bool bf(int x,int D)
{
    for (int i=1;i<=n+1;i++)
        dist[i]=T[i]=inf;
    while (!Q.empty())
        Q.pop();
    dist[x]=0;
    Q.push(x);
    while (!Q.empty())
    {
        x=Q.front();
        Q.pop();
        if (x==D)
            return true;
        for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
            if (dif(x,*i)>0 && dist[x]+cost[x][*i]<dist[*i])
            {
                dist[*i]=dist[x]+cost[x][*i];
                T[*i]=x;
                Q.push(*i);
            }
    }
    return false;
}

int flow(int S,int D)
{
    int C=0,M;
    while (bf(S,D))
    {
        M=inf;
        for (int i=D;i!=S;i=T[i])
            M=min(M,dif(T[i],i));
        for (int i=D;i!=S;i=T[i])
        {
            flux[T[i]][i]+=M;
            flux[i][T[i]]-=M;
            C+=M*cost[T[i]][i];
        }
    }
    return C;
}

inline int scor (int x,int y,int z)
{
    return (x && y && (!z || x+y<z)) ? x+y : z;
}

void bellman_ford(int dist[],int x)
{
    int y,c;
    for (int i=1;i<=n;i++)
        dist[i]=inf;
    dist[x]=0;
    Q.push(x);
    while (!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for (vector<Muchie>::iterator i=b[x].begin();i!=b[x].end();i++)
        {
            y=(*i).y;
            c=(*i).c;
            if (dist[x]+c<dist[y])
            {
                dist[y]=dist[x]+c;
                Q.push(y);
            }
        }
    }
}

int main()
{
    int m,x,y,c,C=0;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y>>c;
        b[x].push_back((Muchie){y,c});
        C+=c;
        grad[x]++;
        grad[y]--;
    }
    for (int i=1;i<=n;++i)
        bellman_ford(drum[i],i);
    for (int i=1;i<=n;i++)
        if (grad[i]<0)
        {
            cap[0][i]=-grad[i];
            a[0].push_back(i);
            a[i].push_back(0);
            for (int j=1;j<=n;j++)
                if (grad[j]>0)
                {
                    cap[i][j]=inf;
                    cost[i][j]=drum[i][j];
                    a[i].push_back(j);
                    a[j].push_back(i);
                }
        }
        else
        {
            cap[i][n+1]=grad[i];
            a[n+1].push_back(i);
            a[i].push_back(n+1);
        }
    out<<C+flow(0,n+1)<<"\n";
    return 0;
}