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

#define DIM 64
#define INF (1 << 30)

using namespace std;

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

int n, m;

int source, destination;

vector< pair<int, int> > L[DIM];
vector<int> L2[DIM];

int grad[DIM];

int capacity[DIM][DIM], cost[DIM][DIM], flux[DIM][DIM];

int parent[DIM], d[DIM];

bool vis[DIM];

struct cmp {

    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {

        return a.second > b.second;

    }

};

priority_queue<pair<int, int>, vector< pair<int, int> > , cmp> H;

void dijkstra(int cnode) {

    for (int i = 1; i <= n; i++)
        cost[cnode][i] = INF;

    memset(vis, false, sizeof vis);

    cost[cnode][cnode] = 0;

    H.push(make_pair(cnode, 0));

     while (H.size()) {

        int node = H.top().first;

        H.pop();

        if (vis[node])
            continue;

        vis[node] = true;

        for (int i = 0; i < L[node].size(); i++) {

            int child = L[node][i].first;

            if(cost[cnode][child] > cost[cnode][node] + L[node][i].second) {

                cost[cnode][child] = cost[cnode][node] + L[node][i].second;

                H.push(make_pair(child, cost[cnode][child]));

            }

        }

     }

}

bool BF() {

    queue<int> Q;

    for (int i = source; i <= destination; i++) {

        parent[i] = 0;
        d[i] = INF;

    }

    parent[0] = -1;
    d[0] = 0;

    Q.push(0);

    while (Q.size()) {

        int node = Q.front();

        Q.pop();

        for (int i = 0; i < L2[node].size(); i++) {

            int child = L2[node][i];
            int C = cost[node][child];

            if (capacity[node][child] > flux[node][child] && d[node] + C < d[child]) {

                d[child] = d[node] + C;
                parent[child] = node;

                Q.push(child);

            }


        }

    }

    return (d[destination] != INF);

}

int main () {

    fin >> n >> m;

    int solution = 0;

    for(int i = 1; i <= m; i++) {

        int x, y, c;

        fin >> x >> y >> c;

        solution += c;

        L[x].push_back(make_pair(y, c));
        L[y].push_back(make_pair(x, c));

        grad[x]++;
        grad[y]--;

    }

    source = 0;

    destination = n + 1;

    for (int i = 1; i <= n; i++) {

        if(grad[i] >= 0) {

            L2[source].push_back(i);
            L2[i].push_back(source);

            capacity[source][i] = grad[i];

        }else {

            L2[i].push_back(destination);
            L2[destination].push_back(i);

            capacity[i][destination] = -grad[i];

        }

    }

    for (int i = 0; i < L2[source].size(); i++) {

        for (int j = 0; j < L2[destination].size(); j++) {

            int node1 = L2[source][i];
            int node2 = L2[destination][j];

            L2[node1].push_back(node2);
            L2[node2].push_back(node1);

            capacity[node1][node2] = INF;

        }

    }

    for(int i = 1; i <= n; i++) {

        dijkstra(i);

    }

    while (BF()) {

        int var = parent[destination];

        if (capacity[var][destination] <= flux[var][destination])
            continue;


        int minim = capacity[var][destination] - flux[var][destination];

        while (parent[var] != -1){

            minim = min(minim, capacity[parent[var]][var] - flux[parent[var]][var]);

            var = parent[var];

        }

        var = parent[destination];
        flux[var][destination] += minim;
        flux[destination][var] -= minim;

        while (parent[var] != -1){

            flux[parent[var]][var] += minim;
            flux[var][parent[var]] -= minim;

            var = parent[var];

        }

        solution += d[destination] * minim;

    }

    fout << solution << "\n";

    return 0;

}

//Miriam e tare!