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

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

using namespace std;

vector <int> G[MAXN];

struct mystruct{
    int from, to,  price;

    bool operator < (const mystruct &aux) const {
        return price < aux.price;
    }
} edges[MAXM];

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;

    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 = 1;
    sink = n+1;

    for(i=1; i<=m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        if(y == 1) y = n+1;

        G[x].push_back(y);
        G[y].push_back(x);
        capacity[x][y] = 1;
        cost[x][y] = z;
        cost[y][x] = -z;

        if(y == n+1) y = 1;
        edges[i] = {x, y, z};

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

    sort(edges+1, edges+m+1);

    f = 0;
    for(i=1; i<=n && !f; ++i)
        if(in[i] != out[i])
            f = 1;

    while(f) {
        f = 0;
        for(i=1; i<=m &&!f; ++i)
            if(in[edges[i].to] < out[edges[i].to] && out[edges[i].from] < in[edges[i].from]) {
                f = 1;
                out[edges[i].from]++;
                in[edges[i].to]++;
                capacity[edges[i].from][edges[i].to]++; } }

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

    printf("%d", mincost);

    return 0;
}