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

const int SIZE = 6e1 + 5;
const int INFI = 0x3f3f3f3f;

int start_node, finish_node, nr_nodes, nr_nodes1, nr_nodes2, node1, node2, edge_cost, minim, answer, nr_edges;
int cost[SIZE][SIZE], capacity[SIZE][SIZE], flow[SIZE][SIZE], father[SIZE], dist[SIZE][SIZE], dp[SIZE];
int indegree[SIZE], outdegree[SIZE], my_vector[SIZE];

std::vector <int> edge[SIZE]; std::bitset <SIZE> marked; std::deque <int> my_queue;

inline bool bf( int start_node, int finish_node ) {
    bool ok = false;
    marked.reset(); marked[start_node] = 1;
    my_queue.clear(); my_queue.push_back(start_node);
    memset( dp, INFI, sizeof(dp) ); dp[start_node] = 0;
    
    while( !my_queue.empty() ) {
        int node = my_queue.front();
        
        std::vector <int> :: iterator it;
        for( it = edge[node].begin(); it != edge[node].end(); it ++ ) {
            int next_node = *it;
            
            if( flow[node][next_node] == capacity[node][next_node] )
                continue;
            
            if( dp[next_node] > dp[node] + cost[node][next_node] ) {
                dp[next_node] = dp[node] + cost[node][next_node];
                father[next_node] = node;
                
                if( !marked[next_node] ) {
                    marked[next_node] = 1;
                    my_queue.push_back(next_node);
                    
                    if( next_node == finish_node )
                        ok = true;
                }
            }
        }
        
        marked[node] = 0;
        my_queue.pop_front();
    }
    
    return ok;
}

int main( int argc, const char *argv[] ) {
    
    freopen( "traseu.in" , "r", stdin  );
    freopen( "traseu.out", "w", stdout );
    
    scanf( "%d %d", &nr_nodes, &nr_edges );
    memset( dist, INFI, sizeof(dist) );
    start_node = SIZE - 1; finish_node = SIZE - 2;
    
    for( int i = 1; i <= nr_edges; i ++ ) {
        scanf( "%d %d %d", &node1, &node2, &edge_cost ); answer += edge_cost;
        indegree[node2] ++; outdegree[node1] ++; dist[node1][node2] = edge_cost;
    }
    
    for( int k = 1; k <= nr_nodes; k ++ ) {
    for( int i = 1; i <= nr_nodes; i ++ ) {
    for( int j = 1; j <= nr_nodes; j ++ ) {
        if( i == k || j == k ) continue;
    
        if( dist[i][j] > dist[i][k] + dist[k][j] )
            dist[i][j] = dist[i][k] + dist[k][j];
    }}}
    
    nr_nodes2 = nr_nodes1;
    for( int i = 1; i <= nr_nodes; i ++ ) {
        if( indegree[i] > outdegree[i] ) {
            my_vector[++nr_nodes1] = i;
        
            capacity[start_node][nr_nodes1] = indegree[i] - outdegree[i];
            edge[start_node].push_back(nr_nodes1);
            edge[nr_nodes1].push_back(start_node);
        }
    }
    
    nr_nodes2 = nr_nodes1;
    for( int i = 1; i <= nr_nodes; i ++ ) {
        if( indegree[i] < outdegree[i] ) {
            my_vector[++nr_nodes2] = i;
            
            capacity[nr_nodes2][finish_node] = outdegree[i] - indegree[i];
            edge[finish_node].push_back(nr_nodes2);
            edge[nr_nodes2].push_back(finish_node);
        }
    }
    
    for( int i = 1; i <= nr_nodes1; i ++ ) {
    for( int j = nr_nodes1 + 1; j <= nr_nodes2; j ++ ) {
        capacity[i][j] = INFI;
        cost[i][j] = +dist[ my_vector[i] ][ my_vector[j] ];
        cost[j][i] = -dist[ my_vector[i] ][ my_vector[j] ];
    
        edge[i].push_back(j);
        edge[j].push_back(i);
    }}
    
    while( bf(start_node, finish_node) ) {
        minim = INFI;
        
        for( int node = finish_node; node != start_node; node = father[node] )
            minim = std::min( minim, capacity[ father[node] ][node] - flow[ father[node] ][node] );
        
        for( int node = finish_node; node != start_node; node = father[node] ) {
            answer += minim * cost[ father[node] ][node];
            flow[ father[node] ][node] += minim;
            flow[node][ father[node] ] -= minim;
        }
    }
    
    printf( "%d\n", answer );
    
    return 0;
}