#!/usr/bin/python3

"""
WA submission.

Track the number of disks incident to each node.

Repeatedly try increasing the number of disks on each node by 1.
Sort the nodes according to the number of incident disks.
For each node, take a disk from the edge whose other end point
has the largest number of disks available.
After taking a disk, update the number of disks available to the
other node incident to the edge that we took a disk from.

Time complexity: O((n log n + m) * b_max)
"""

import heapq
from sys import stdin


class Edge:
    def __init__(self, u, v, b):
        self.u = u
        self.v = v
        self.b = b


class Node:
    def __init__(self, idd):
        self.id = idd
        self.adj = []
        self.available = 0


def main():
    n, m = map(int, stdin.readline().split(" "))
    edges = []
    for _ in range(m):
        u, v, b = map(int, stdin.readline().split(" "))
        edges.append(Edge(u - 1, v - 1, b))
    nodes = [Node(i) for i in range(n)]
    total_beads = 0
    for edge in edges:
        nodes[edge.u].adj.append(edge)
        nodes[edge.u].available += edge.b
        nodes[edge.v].adj.append(edge)
        nodes[edge.v].available += edge.b
        total_beads += edge.b
    available_min = min(node.available for node in nodes)
    beads_on_each_node = 0
    finished = False
    while available_min > 0:
        pq = []
        processed = set()
        for node in nodes:
            heapq.heappush(pq, (node.available, node.id))
        while len(processed) < n:
            available, node_id = heapq.heappop(pq)
            while node_id in processed:
                available, node_id = heapq.heappop(pq)
            if available == 0:
                finished = True
                break
            best_available = None
            best_edge = None
            best_other_node_id = None
            for edge in nodes[node_id].adj:
                if edge.b == 0:
                    continue
                other_node_id = edge.v
                if other_node_id == node_id:
                    other_node_id = edge.u
                if best_available is None or nodes[other_node_id].available > best_available:
                    best_available = nodes[other_node_id].available
                    best_edge = edge
                    best_other_node_id = other_node_id
            if not best_available:
                finished = True
                break
            best_edge.b -= 1
            nodes[node_id].available -= 1
            nodes[best_other_node_id].available -= 1
            # print(f"Pushing 1 disk from edge ({node_id+1},{best_other_node_id+1}) to {node_id+1}")
            heapq.heappush(pq, (nodes[best_other_node_id].available, best_other_node_id))
            processed.add(node_id)
        if finished:
            break
        beads_on_each_node += 1

    print(total_beads - n * beads_on_each_node)


if __name__ == "__main__":
    main()