from collections import deque

INF = int(1e9)

class Dinitz:
    def __init__(self, n):
        # dst, cap, rev_edge
        self.graph = [[] for _ in range(n)]
        self.level = [0 for _ in self.graph]

    def add_edge(self, u, v, cap, rev_cap = 0):
        self.graph[u].append((v, cap, len(self.graph[v])))
        self.graph[v].append((u, rev_cap, len(self.graph[u]) - 1))

    def bfs(self, src, sink):
        self.level = [0 for _ in self.graph]

        q = deque([src])
        self.level[src] = 1
        while q:
            u = q.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and self.level[v] == 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)

        return self.level[sink] > 0

    def dfs(self, u, sink, cur_flow):
        if u == sink or cur_flow == 0:
            return cur_flow

        for i, (v, cap, rev_edge) in enumerate(self.graph[u]):
            if self.level[v] != self.level[u] + 1:
                continue

            f = self.dfs(v, sink, min(cur_flow, cap))
            if f > 0:
                self.graph[u][i] = (v, cap - f, rev_edge)

                rev_cap = self.graph[v][rev_edge][1]
                assert self.graph[v][rev_edge][2] == i
                self.graph[v][rev_edge] = (u, rev_cap + f, i)

                return f

        return 0

    def flow(self, src, sink):
        res = 0
        while self.bfs(src, sink):
            while True:
                f = self.dfs(src, sink, INF)
                if not f:
                    break

                res += f

        return res


def can(n, edges, balance):
    # bipartite graph
    # src -> wire with cap w
    # wire -> sphere with cap inf
    # sphere -> sink with cap balance
    # valid iff flow == balance * n

    m = len(edges)
    src = n + m
    sink = src + 1

    dinitz = Dinitz(sink + 1)
    for i, (u, v, w) in enumerate(edges):
        dinitz.add_edge(src, i, w)
        dinitz.add_edge(i, u + m, INF)
        dinitz.add_edge(i, v + m, INF)

    for u in range(n):
        dinitz.add_edge(u + m, sink, balance)

    flow = dinitz.flow(src, sink)
    return flow == balance * n


def main():
    n, m = map(int, input().split())

    beads = 0
    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        beads += w
        edges.append((u, v, w))

    lo = 0
    hi = beads + 1
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if can(n, edges, mid):
            lo = mid
        else:
            hi = mid

    print(beads - n * lo)


if __name__ == "__main__":
    main()