#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;
vector<int> a[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;
}

void roy()
{
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (i!=j && (!drum[i][j] || drum[i][j]>drum[i][k]+drum[k][j]))
                    drum[i][j]=drum[i][k]+drum[k][j];
}

int main()
{
    int m,x,y,c,C=0;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y>>c;
        drum[x][y]=c;
        C+=c;
        grad[x]++;
        grad[y]--;
    }
    roy();
    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;
}