#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int DIM = 62;

int cost[DIM][DIM];
int in[DIM];
int out[DIM];

struct Edge
{
    int x;
	int y;
	int cap;
	int cost;
};

struct Network
{
    vector <Edge> edges;
    vector <vector <int> > adj;

    vector <int> dist;

    int n, S, D;

	Network(int n, int S, int D) : n(n), S(S), D(D), adj(n + 1), dist(n + 1, INF) {}

	void add_edge(int x, int y, int c, int z)
    {
        adj[x].emplace_back(edges.size());
        edges.emplace_back(Edge{x, y, c, z});

        adj[y].emplace_back(edges.size());
        edges.emplace_back(Edge{y, x, 0, -z});
    }

    void bellman_ford()
    {
        vector <bool> inQ(n + 1, false);
        queue <int> q;

        q.push(S);
        inQ[S] = true;

        dist[S] = 0;

        while(!q.empty())
		{
            int nod = q.front();
            q.pop();

            inQ[nod] = false;

            for(auto i : adj[nod])
			{
                if(edges[i].cap && dist[edges[i].y] > dist[nod] + edges[i].cost)
				{
                    dist[edges[i].y] = dist[nod] + edges[i].cost;

                    if(!inQ[edges[i].y])
					{
                        inQ[edges[i].y] = true;
                        q.push(edges[i].y);
                    }
                }
            }
        }
    }

    bool dijkstra(vector <int>& dad)
    {
        dad = vector <int> (n + 1, -1);
        vector <int> cost(n + 1, INF);

        priority_queue <pair <int, int> > pq;

        cost[S] = 0;

        pq.push({0, S});

        while(!pq.empty())
		{
            int nod = pq.top().second;
			int val = pq.top().first;

			pq.pop();

            if(val != -cost[nod])
			{
                continue;
            }

            for(auto i : adj[nod])
			{
                if(edges[i].cap && cost[edges[i].y] > cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost)
				{
                    cost[edges[i].y] = cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost;

                    pq.push({-cost[edges[i].y], edges[i].y});
                    dad[edges[i].y] = i;
                }
            }
        }

        for(int i = 1; i <= n; i++)
		{
            dist[i] += cost[i];
		}

        return (dad[D] != -1);
    }

	int get_cost()
    {
        bellman_ford();

        int cost = 0;

        vector <int> dad;

        while(dijkstra(dad))
		{
            int cat = INF;

            for(int i = dad[D]; i != -1; i = dad[edges[i].x])
                cat = min(cat, edges[i].cap);

            for (int i = dad[D]; i != -1; i = dad[edges[i].x])
			{
                cost += cat * edges[i].cost;
                edges[i].cap -= cat;
                edges[i ^ 1].cap += cat;
            }
        }

        return cost;
    }

};

main()
{
    int n, m;
    fin >> n >> m;

    int ans = 0;

    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;

        cost[x][y] = c;
        ans += c;

        ++out[x];
        ++in[y];
    }

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

    Network retea(n + 2, n + 1, n + 2);

    for(int i = 1; i <= n; ++i)
        if(in[i] > out[i])
        {
            retea.add_edge(n + 1, i, in[i] - out[i], 0);

            for(int j = 1; j <= n; ++j)
                if(out[j] > in[j])
                    retea.add_edge(i, j, INF, cost[i][j]);
        }
        else
            if(out[i] > in[i])
            {
                retea.add_edge(i, n + 2, out[i] - in[i], 0);
            }

    fout << ans + retea.get_cost();
}