import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class BalancingTLE_Bon {

	public static class Graph
	{
		private static final int INF = 100000000;

		private Vertex[] vertices;
		private int n, m;		// number of vertices, edges

		public Graph(int n, int m)
		//
		// vertices: 1...n
		// edges: n+1..n+m
		// initial source: n+m+2
		// split source vertex: n+m+1
		// sink: 0;
		{
			this.n=n;
			this.m = m;
			vertices = new Vertex[n+m+3];
			for(int i=0; i<n+m+3; i++)
				vertices[i] = new Vertex("", i);
		}
		
		public String toString()
		{
			String ans = "";
			for(Vertex v : vertices) {
				ans += v.num + ":";
				for(Edge e : v.edges) {
					ans += " " + e.w + "(" + e.capacity + ")";
				}
				ans += "\n";
			}
			return ans;
		}

		public void addEdge(int v, int w, int capacity)
		{
			Edge e = new Edge(v, w, capacity, null);
			vertices[v].addEdge(e);
			Edge reverse = new Edge(w, v, 0, e);
			vertices[w].addEdge(reverse);				// capacity=0 edge is non-existent edge
			e.reverseEdge = reverse;
		}
		
		public void reset(int balanceNum)
		{
			for(Vertex v : vertices) {			// reset forward edge capacities to initial values, reverse edge capacities = 0
				for(Edge e : v.edges)
					if (e.w < v.num) {
						e.capacity += e.reverseEdge.capacity;
						e.reverseEdge.capacity = 0;
					}				
			}
			vertices[n+m+2].edges.get(0).capacity = n*balanceNum;	// set capacity of single edge leaving sink
			for(int i=1; i<=n; i++) {
				int numedges = vertices[i].edges.size();
				vertices[i].edges.get(numedges-1).capacity = balanceNum;	// set capacities from vertex vertices to sink
			}
		}
		
		ArrayList<Edge> p;
		
		public int maxFlow(int source, int sink, int balanceNum)
		{
			reset(balanceNum);
			int totalFlow = 0;
			p = new ArrayList<>();
//			System.out.println("Current graph:");
//			System.out.println(this);
			while (getPath(source, sink, -1)) {
				int minFlow = getMinFlow();
//				System.out.print("path = " + source);
//				for(Edge e : p) {
//					System.out.print(" " + e.w);
//				}
//				System.out.println(", minflow = " + minFlow);
				totalFlow += minFlow;
				for(Edge pathEdge : p) {
					Vertex start = vertices[pathEdge.v];
					Vertex end = vertices[pathEdge.w];
					int i=0;
					Edge e = start.edges.get(i);
					while (e.w != pathEdge.w) {
						e = start.edges.get(++i);
					}
					e.capacity -= minFlow;					// edges where capacity == 0 will be ignored
					i=0;
					e = end.edges.get(i);
					while (e.w != pathEdge.v) {
						e = end.edges.get(++i);
					}
					e.capacity += minFlow;
				}
				p.clear();
//				System.out.println("Current graph:");
//				System.out.println(this);
}
			return totalFlow;
		}
		
		public int getMinFlow()
		{
			int flow = Integer.MAX_VALUE;
			for(Edge e : p) {
				if (e.capacity < flow)
					flow = e.capacity;
			}
			return flow;
		}
		
		public boolean getPath(int v1, int v2, int prev)
		{
			for(Edge e : vertices[v1].edges) {
				if (e.capacity == 0 || e.w == prev)				// 0-capacity edges don't exist - honsetly!
					continue;
				if (p.contains(e))
					continue;
//				System.out.println("adding " + e.v + "-" + e.w);
				p.add(e);
				if (e.w == v2)
					return true;
				if (getPath(e.w, v2, v1))
					return true;
				p.remove(e);
//				System.out.println("removing " + e.v + "-" + e.w);
			}
			return false;
		}	
	}

	public static class Vertex
	{
		String name;
		int num;
		ArrayList<Edge> edges;

		public Vertex(String name, int num)
		{
			this.name = name;
			this.num = num;
			edges = new ArrayList<Edge>();
		}

		public void addEdge(Edge e)
		{
			edges.add(e);
		}
	}

	public static class Edge
	{
		int v, w;
		int capacity;
		Edge reverseEdge;

		public Edge(int v, int w, int c, Edge reverseEdge)
		{
			this.v = v;
			this.w = w;
			capacity = c;
			this.reverseEdge = reverseEdge;
		}
	}
	
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		
		Graph g = new Graph(n, m);
		int totalBeads = 0;
		for(int i=1; i<=m; i++) {
			int v1 = in.nextInt();
			int v2 = in.nextInt();
			int beads = in.nextInt();
			g.addEdge(n+i, v1, beads);
			g.addEdge(n+i, v2, beads);
			g.addEdge(n+m+1, n+i, beads);	// link splitter to edge vertices
			totalBeads += beads;
		}
		for(int i=1; i<=n; i++)			// link vertex vertices = sink
			g.addEdge(i, 0, 0);
		g.addEdge(n+m+2, n+m+1, 0);
//		System.out.println(g);
		
		int balanceNum = totalBeads/n;
		while (balanceNum > 0) {
//			System.out.println("Try balanceNum = " + balanceNum);
			if (g.maxFlow(n+m+2, 0, balanceNum) == n*balanceNum) {
				break;
			}
			balanceNum--;
		}
		System.out.println(totalBeads - n*balanceNum);

	}

}