#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define MAXN 70
#define INF 1000000000
using namespace std;
vector<int> g[MAXN];
queue<int> Queue;
int n,answer=0;
int capacity[MAXN][MAXN],flow[MAXN][MAXN],cost[MAXN][MAXN];
int in[MAXN],out[MAXN],inQueue[MAXN],dad[MAXN],best[MAXN],source,sink;
void AddEdge(int a,int b,int c){
    g[a].push_back(b);
    g[b].push_back(a);
    capacity[a][b]=INF;
    cost[a][b]=c;
    cost[b][a]=-c;
    out[a]++;
    in[b]++;
}
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
bool BellmanFord(){
    int i,node;
    for(i=0;i<=n+1;i++)
        best[i]=INF;
    memset(inQueue,0,sizeof(inQueue));
    memset(dad,0,sizeof(dad));
    best[source]=0;
    Queue.push(source);
    inQueue[source]=1;
    while(!Queue.empty()){
        node=Queue.front();
        Queue.pop();
        for(i=0;i<g[node].size();i++)
            if(capacity[node][g[node][i]]!=flow[node][g[node][i]]&&best[node]+cost[node][g[node][i]]<best[g[node][i]]){
                best[g[node][i]]=best[node]+cost[node][g[node][i]];
                dad[g[node][i]]=node;
                if(inQueue[g[node][i]]==0){
                    inQueue[g[node][i]]=1;
                    Queue.push(g[node][i]);
                }
            }
        inQueue[node]=0;
    }
    if(best[sink]==INF)
        return false;
    return true;
}
int MaximumFlowMinimumCost(){
    int answer=0,add,node;
    while(BellmanFord()==true){
        add=INF;
        for(node=sink;node!=source;node=dad[node])
            add=minimum(add,capacity[dad[node]][node]-flow[dad[node]][node]);
        for(node=sink;node!=source;node=dad[node]){
            flow[dad[node]][node]+=add;
            flow[node][dad[node]]-=add;
        }
        answer=answer+add*best[sink];
    }
    return answer;
}
int main(){
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);
    int m,i,a,b,c;
    scanf("%d%d",&n,&m);
    source=0;
    sink=n+1;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        AddEdge(a,b,c);
        answer+=c;
    }
    for(i=1;i<=n;i++){
        if(in[i]>out[i]){
            g[source].push_back(i);
            g[i].push_back(source);
            capacity[source][i]=in[i]-out[i];
            cost[source][i]=cost[i][source]=0;
        }
        if(in[i]<out[i]){
            g[sink].push_back(i);
            g[i].push_back(sink);
            capacity[i][sink]=out[i]-in[i];
            cost[sink][i]=cost[i][sink]=0;
        }
    }
    answer+=MaximumFlowMinimumCost();
    printf("%d",answer);
    return 0;
}