/**
 * 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.
 * Use Dinitz' Algorithm for the max flow algorithm.
 *
 * This submission gets TLE because it does not binary search on the balance
 * number.
 *
 * The graph for the flow algorithm has (m + n + 2) vertices and
 * (m + 2*m + n) = 3*m + n edges. Dinitz' Algorithm has time complexity
 * O(sqrt(V)E) for bipartite graphs. So we have a time complexity of:
 * O((disksTotal/n) * sqrt(m + n + 2)*(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 = 0L
    for (rawEdge in rawEdges) {
        disksTotal += rawEdge[2]
    }
    var hi = disksTotal / n.toLong()
    var lo = 1L
    var best = 0L
    while (lo <= hi) {
        val mid = lo

        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.toDouble())
            addEdge(graph, edgeIndex, m + v, disksTotal.toDouble())

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

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

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

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

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

fun maxFlow(graph: Array<ArrayList<Edge>>, src: Int, sink: Int): Double {
    var flow = 0.0
    var dist = IntArray(graph.size)
    while (dinitzBfs(graph, src, sink, dist)) {
        var pointer = IntArray(graph.size)
        while (true) {
            val df = dinitzDfs(graph, pointer, dist, sink, src, Double.MAX_VALUE)
            if (df == 0.0) {
                break
            }
            flow += df
        }
    }
    return flow
}

fun dinitzBfs(graph: Array<ArrayList<Edge>>, src: Int, sink: Int, dist: IntArray): Boolean {
    dist.fill(-1)
    dist[src] = 0
    var q = IntArray(graph.size)
    var size = 0
    q[size++] = src
    var i = 0
    while (i<size) {
        for (edge in graph[q[i]]) {
            if (dist[edge.v] < 0 && edge.flow < edge.capacity) {
                dist[edge.v] = dist[q[i]] + 1
                q[size++] = edge.v
            }
        }
        i++
    }
    return dist[sink] >= 0
}

fun dinitzDfs(graph: Array<ArrayList<Edge>>, pointer: IntArray, dist: IntArray, sink: Int, u: Int, flow: Double): Double {
    if (u == sink) {
        return flow
    }
    while (pointer[u] < graph[u].size) {
        var edge = graph[u].get(pointer[u])
        if (dist[edge.v] == dist[u] + 1 && edge.flow < edge.capacity) {
            val df = dinitzDfs(graph, pointer, dist, sink, edge.v, min(flow, edge.capacity - edge.flow))
            if (df > 0) {
                edge.flow += df
                graph[edge.v].get(edge.rev).flow -= df
                return df
            }
        }
        pointer[u]++
    }
    return 0.0
}