#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

#define MAXN 62
#define MAXM 2000
#define INF 0x3f3f3f3f

using namespace std;

vector <int> G[MAXN];

int n, m, source, sink, maxflow, mincost, flow[MAXN][MAXN], capacity[MAXN][MAXN], cost[MAXN][MAXN], dad[MAXN], dist[MAXN];
int in[MAXN], out[MAXN], q[MAXN*MAXN];
bool inq[MAXN];

inline bool bellmanford()
{
    int node, i, son, left, right;

    memset(dad, 0, sizeof dad);
    for(i=1; i<=n+1; i++)
        dist[i] = INF;
    dist[source] = 0;
    left = right = 0;
    q[right++] = source;
    inq[source] = 1;

    while(left < right) {
        node = q[left++];
        inq[node] = 0;
        if(node == sink) continue;
        for(i=0; i<G[node].size(); ++i) {
            son = G[node][i];
            if(flow[node][son] < capacity[node][son] && dist[node] + cost[node][son] < dist[son]) {
                dist[son] = dist[node] + cost[node][son];
                dad[son] = node;
                if(!inq[son]) q[right++] = son, inq[son] = 1; } } }

    return dist[sink] != INF;
}

inline int pump()
{
    int node, minflow = INF;

    for(node=sink; node!=source; node=dad[node])
        minflow = min(minflow, capacity[dad[node]][node] - flow[dad[node]][node]);
    if(minflow)
        for(node=sink; node!=source; node=dad[node])
            flow[dad[node]][node] += minflow, flow[node][dad[node]] -= minflow;

    mincost += dist[sink]*minflow;

    return minflow;
}

int main()
{
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);

    int i, x, y, z, f;

    scanf("%d%d", &n, &m);

    source = 0;
    sink = n+1;

    for(i=1; i<=m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        G[x].push_back(y);
        G[y].push_back(x);
        capacity[x][y] = INF;
        cost[x][y] = z;
        cost[y][x] = -z;
        mincost += z;

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

   for(i=1; i<=n; ++i)
   {
       if(out[i] < in[i]) {
            G[source].push_back(i);
            G[i].push_back(source);
            capacity[source][i] = in[i] - out[i]; }
        if(out[i] > in[i]) {
            G[sink].push_back(i);
            G[i].push_back(sink);
            capacity[i][sink] = out[i] - in[i]; } }

    while(bellmanford()) maxflow += pump();

    printf("%d", mincost);

    return 0;
}