#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define INF 1000000000
#define S 0
#define D 61
#define nodesMax 63

#define pb push_back
#define mkp make_pair


using namespace std;

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

int n, m, Sol;
int gIn[nodesMax], gOut[nodesMax], viz[nodesMax], dist[nodesMax], C[nodesMax][nodesMax], Cost[nodesMax][nodesMax], TT[nodesMax];
vector<int> G[nodesMax], sNodes, dNodes;
queue<int> Q;

bool bellmanFord()
{
    for(int i=1; i<nodesMax; i++)
        dist[i]=INF;
    Q.push(S);

    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        viz[node]=0;

        for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
        {
            int fiu=*it;
            if(C[node][fiu]!=0 && dist[node]+Cost[node][fiu]<dist[fiu])
            {
                dist[fiu]=dist[node]+Cost[node][fiu];
                TT[fiu]=node;
                if(viz[fiu]==0)
                {
                    viz[fiu]=1;
                    Q.push(fiu);
                }
            }
        }
    }

    return (dist[D]!=INF);
}

int main()
{
    int a, b, c;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b;
        fin>>Cost[a][b];
        gOut[a]++, gIn[b]++;
        Sol+=Cost[a][b];
    }

    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(Cost[i][k] && Cost[k][j] && (Cost[i][k]+Cost[k][j]<Cost[i][j] || (Cost[i][j]==0)) && i!=j)
                    Cost[i][j]=Cost[i][k]+Cost[k][j];

    for(int i=1; i<=n; i++)
    {
        if(gOut[i]>gIn[i])
        {
            dNodes.pb(i);
            G[i].pb(D);
            C[i][D]=gOut[i]-gIn[i];
        }
        if(gOut[i]<gIn[i])
        {
            sNodes.pb(i);
            G[S].pb(i);
            C[S][i]=gIn[i]-gOut[i];
        }
    }

    for(vector<int>::iterator it1=sNodes.begin(); it1!=sNodes.end(); it1++)
    {
        int node1=*it1;
        for(vector<int>::iterator it2=dNodes.begin(); it2!=dNodes.end(); it2++)
        {
            int node2=*it2;
            G[node1].pb(node2);
            G[node2].pb(node1);
            C[node1][node2]=INF;
            Cost[node2][node1]=-Cost[node1][node2];
        }
    }

    while(bellmanFord())
    {
        int flow=INF;
        for(int aux=D; aux!=S; aux=TT[aux])
            flow=min(flow, C[TT[aux]][aux]);

        for(int aux=D; aux!=S; aux=TT[aux])
        {
            C[TT[aux]][aux]-=flow;
            C[aux][TT[aux]]+=flow;
        }

        Sol+=flow*dist[D];
    }

    fout<<Sol;
}