#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct edge{
  int from;
  int to;
};

struct flow_edge{
  int capacity;
  int flow_used;
};


void Print_Flow_Graph(const vector<vector<flow_edge> >& G){
  for(int i = 0; i < G.size(); i++){
    for(int j = 0; j < G[i].size(); j++){
      if(G[i][j].capacity > 0){
	cout << "(" << i << "," << j << "): " << G[i][j].flow_used << "/" << G[i][j].capacity << endl;
      }
    }
  }
}

vector<int> Calc_Components(const vector<vector<int> >& Adj, int source, vector<bool>& reached){
  vector<int> stack;
  stack.push_back(source);
  reached[source] = true;
  vector<int> found;
  while(stack.size() != 0){
    int cur = stack[stack.size()-1];
    found.push_back(cur);
    stack.pop_back();
   
    for(int i = 0; i < Adj.size(); i++){
      if(Adj[cur][i] >= 0  && !reached[i]){
	stack.push_back(i);
	reached[i] = true;
      }
    }
  }

  return found;
}

void Build_Flow_Graph(const vector<int>& component, const vector<vector<int> >& beads, vector<vector<flow_edge> >& Flow_Graph, const vector<edge>& edge_list, int desired_flow){
 
  int edge_count = edge_list.size();
  Flow_Graph.resize(beads.size() + edge_list.size()+2);
  flow_edge empty;
  empty.capacity = 0;
  empty.flow_used = 0;
  for(int i = 0; i < Flow_Graph.size(); i++)
    Flow_Graph[i].resize(Flow_Graph.size(), empty);

  // now to add the capacities
  
  // vertex 0 is the source, it goes to all edge vertices
  // with capacity = the # of beads on that edge
  for(int i = 1; i <= edge_count; i++){
    edge this_edge = edge_list[i-1];
    Flow_Graph[0][i].capacity = beads[this_edge.from][this_edge.to];

    // each edge goes to its vertices at a capacity equal to the # of beads in
    // the edge

  
    Flow_Graph[i][edge_count+1+this_edge.from].capacity = beads[this_edge.from][this_edge.to];
    Flow_Graph[i][edge_count+1+this_edge.to].capacity = beads[this_edge.from][this_edge.to];
  }
  // each vertex connects to the sink at a capacity of our desired capacity
  for(int i = 0; i < component.size(); i++){
    Flow_Graph[edge_count+1+component[i]][Flow_Graph.size()-1].capacity = desired_flow;
  }
}

void Calculate_Residual(const vector<vector<flow_edge> >& G, vector<vector<flow_edge> >& residual){
  residual.resize(G.size());
  flow_edge empty;
  empty.flow_used = 0;
  empty.capacity = 0;
  for(int i = 0; i < G.size(); i++){
    residual[i].resize(G.size(), empty);
  }
  for(int i = 0; i < residual.size(); i++)
    for(int j = 0; j < residual.size(); j++){
      if(G[i][j].capacity > 0)
	residual[i][j].capacity = G[i][j].capacity-G[i][j].flow_used;
      else if(G[j][i].capacity > 0)
	residual[i][j].capacity = G[j][i].flow_used;
      else
	residual[i][j].capacity = 0;
    }
}

bool Find_Path(const vector<vector<flow_edge> > & residual, vector<int>& path){
  vector<int> parent (residual.size(), -1);
  vector<int> queue;
  queue.push_back(0);
  int queue_pos = 0;
  
  while(queue_pos < queue.size()){
    int cur = queue[queue_pos];
    for(int i = 0; i < residual.size(); i++){
      if(parent[i] == -1  && residual[cur][i].capacity > 0){
	queue.push_back(i);
	parent[i] = cur;
	if(i == residual.size()-1)
	  queue_pos = queue.size()+1; // stop searching
      }
    }
    queue_pos++;
  }
  if(parent[parent.size()-1] == -1)
    return false;
  path.resize(0);
  int cur = parent.size()-1;
  path.push_back(cur);
  while(cur != 0){
    cur = parent[cur];
    path.push_back(cur);
  }
  reverse(path.begin(), path.end());
  return true;

}

// can we put enough flow on G so that all of the edges to the sink are at
// capacity?
bool Max_Flow(vector<vector<flow_edge> >& G){
  bool path_found = true;
  vector<vector<flow_edge> > residual;
  Calculate_Residual(G, residual);
  while(path_found){
  
    //   cout << "Flow Graph: " << endl;
    //   Print_Flow_Graph(G);
    //   cout << endl << "Residual: " << endl;
    //    Print_Flow_Graph(residual);
    //      cout << endl;
    
  
    vector<int> path;
    path_found = Find_Path(residual, path);
    if(path_found){
      int flow_cost = residual[path[0]][path[1]].capacity;
   
      for(int i = 1; i < path.size()-1; i++){
	int cur_cost = residual[path[i]][path[i+1]].capacity;
	if(cur_cost < flow_cost)
	  flow_cost = cur_cost;
      }
      //  cout << "Found a path adding " << flow_cost << " flow" << endl;
      for(int i = 0; i < path.size()-1; i++){
	int s = path[i];
	int t = path[i+1];
	if(G[s][t].capacity > 0){ // the edge is in G
	  G[s][t].flow_used += flow_cost;
	
	}
	else{
	  G[s][t].flow_used -= flow_cost;
	 
	}
    
	if(G[s][t].capacity > 0){
	  residual[s][t].capacity = G[s][t].capacity-G[s][t].flow_used;
	  residual[t][s].capacity = G[s][t].flow_used;
	}
	else{ // edge in other direction
	  residual[s][t].capacity = G[t][s].flow_used;
	  residual[t][s].capacity = G[s][t].capacity-G[s][t].flow_used;
	}
	

      }
      
    }
  }
  for(int i = 0; i < G.size(); i++){
    if(G[i][G.size()-1].flow_used != G[i][G.size()-1].capacity)
      return false;
  }
  return true;
}
      

void Adjust_Flow_Graph(vector<vector<flow_edge> >& Flow_Graph, int new_val){

  // reset all flows
  for(int i = 0; i < Flow_Graph.size(); i++){
    for(int j = 0; j < Flow_Graph[i].size(); j++){
      Flow_Graph[i][j].flow_used = 0;
      // reset capacity of vertices connected to sink
      if(j == Flow_Graph[i].size()-1 && Flow_Graph[i][j].capacity != 0)
	Flow_Graph[i][j].capacity = new_val;
    }
  }
}

  
int main(){

  int n;
  // # of vertices
  cin >> n;

  int e;
  // # of edges
  cin >> e;

  vector<vector<int> > beads(n);
  for(int i = 0; i < n; i++){
    beads[i].resize(n, -1);
  }

  int bead_sum = 0;
  // beads on each edge
  for(int i = 0; i < e; i++){
    int from;
    int to;
    int num_beads;
    cin >> from >> to >> num_beads;
    bead_sum += num_beads;
    beads[from-1][to-1] = num_beads;
    beads[to-1][from-1] = num_beads;
  }

  vector<bool> reached(n, false);
  vector<vector<int> > components;

  for(int i = 0; i < n; i++){
    if(!reached[i]){
      vector<int> cur_component = Calc_Components(beads, i, reached);
      components.push_back(cur_component);
    }
  }

  int min_flow = bead_sum/n;

  for(int i = 0; i  < components.size(); i++){
     // the graph will have V+E+2 vertices.
    // so we need to know the # of edges in this component
    int edge_count = 0;
    vector<edge> edge_list;
    for(int j = 0; j < components[i].size(); j++){
      for(int k = j+1; k < components[i].size(); k++)
	if(beads[components[i][j]][components[i][k]] >= 0){
	  edge_count++;
	  edge new_edge;
	  new_edge.from = components[i][j];
	  new_edge.to = components[i][k];
	  edge_list.push_back(new_edge);
	}
    }
   vector<vector<flow_edge> > Flow_Graph;
    Build_Flow_Graph(components[i], beads, Flow_Graph, edge_list, min_flow);
    //    Print_Flow_Graph(Flow_Graph);
    int best_success = 0;
    int low = 1;
    int high = min_flow;
   
    while(low <= high){
      int mid = (low+high)/2;
      //   cout << "Trying to push a flow of: " << mid << endl;
      Adjust_Flow_Graph(Flow_Graph, mid);
      if(Max_Flow(Flow_Graph)){
	if(mid > best_success)
	  best_success = mid;
	low = mid+1;
      }
      else{
	high = mid-1;
      }
    }
    if(best_success < min_flow)
      min_flow = best_success;
  }

  cout << bead_sum - min_flow*n << endl;
  return 0;
}