/**
 * For a given target number of disks to have at each sphere we can use
 * a maximum flow algorithm to determine if it is possible to the disks
 * in this way. Create a bipartite graph where the nodes in one set
 * correspond to the wires and the nodes in the other set correspond to
 * the spheres. We add an edge between a wire node and a sphere node if
 * the wire connects to the sphere. So we have 2 edges for each wire.
 * We also add a source and sink vertex. The source vertex connects
 * to each of the wire edges with a capacity equal to the number of disks
 * on the wire. The sphere nodes each connect to the sink vertex with a
 * capacity equal to the target number of disks. We can determine if
 * the target number is possible by performing a max flow algorithm on
 * the resulting graph and checking if the max flow is equal to the target
 * number multiplied by the number of spheres. Perform a binary search
 * on the target number to more efficiently find the best solution.
 * Use the Ford-Fulkerson Algorithm for the max flow algorithm.
 *
 * The graph for the flow algorithm has (m + n + 2) vertices and
 * (m + 2*m + n) = 3*m + n edges. The Ford-Fulkerson algorithm has time complexity
 * O(E*f) where f is at most the total number of disks. So we have a time complexity of:
 * O(log(disksTotal/n) * disksTotal*(3*m + n)).
 *
 * @author Finn Lidbetter
 */

import kotlin.math.*

fun main() {
    val (n, m) = readln().split(" ").map(){ it -> it.toInt() }
    val rawEdges = Array<IntArray>(m) {
        readln().split(" ").map() { it -> it.toInt() }.toIntArray()
    }
    var disksTotal = 0
    for (rawEdge in rawEdges) {
        disksTotal += rawEdge[2]
    }
    var hi = disksTotal / n
    var lo = 1
    var best = 0
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2

        var graph = createGraph(n + m + 2)
        val src = n + m
        val sink = n + m + 1
        for ((edgeIndex, rawEdge) in rawEdges.withIndex()) {
            val u = rawEdge[0] - 1
            val v = rawEdge[1] - 1
            val disks = rawEdge[2]
            addEdge(graph, edgeIndex, m + u, disksTotal)
            addEdge(graph, edgeIndex, m + v, disksTotal)

            addEdge(graph, src, edgeIndex, disks)
        }
        for (i in 0..n-1) {
            addEdge(graph, m + i, sink, mid)
        }

        if (maxFlow(graph, src, sink) == n * mid) {
            best = mid
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    println(disksTotal - (best*n))
}

class Edge(val v: Int, val rev: Int, val capacity: Int, var flow: Int)

fun createGraph(numNodes: Int): Array<ArrayList<Edge>> {
    val graph = Array<ArrayList<Edge>>(numNodes) {
        arrayListOf<Edge>()
    }
    return graph
}

fun addEdge(graph: Array<ArrayList<Edge>>, u: Int, v: Int, capacity: Int) {
    graph[u].add(Edge(v, graph[v].size, capacity, 0))
    graph[v].add(Edge(u, graph[u].size - 1, 0, 0))
}

fun maxFlow(graph: Array<ArrayList<Edge>>, src: Int, sink: Int): Int {
    var minCut = BooleanArray(graph.size){ false }
    var flow = 0
    while (true) {
        val df = findPath(graph, minCut, src, sink, 987654321)
        if (df == 0) {
            return flow
        }
        minCut = BooleanArray(graph.size) { false }
        flow += df
    }
}

fun findPath(graph: Array<ArrayList<Edge>>, vis: BooleanArray, u: Int, t: Int, f: Int): Int {
    if (u == t) {
        return f
    }
    vis[u] = true
    for (edge in graph[u]) {
        if (!vis[edge.v] && edge.flow < edge.capacity) {
            val df = findPath(graph, vis, edge.v, t, min(f, edge.capacity - edge.flow))
            if (df > 0) {
                edge.flow += df
                graph[edge.v][edge.rev].flow -= df
                return df
            }
        }
    }
    return 0
}