import java.util.Scanner;

public class Balancing_Bon_WA {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		
		int totalBeads = 0;
		int [] maxin = new int[n+1];
		for(int i=1; i<=m; i++) {
			int v1 = in.nextInt();
			int v2 = in.nextInt();
			int beads = in.nextInt();
			totalBeads += beads;
			maxin[v1] += beads;
			maxin[v2] += beads;
		}
		int min = maxin[1];
		for(int i=2; i<=n; i++)
			min = Math.min(min,  maxin[i]);
		
		int balanceNum = totalBeads/n;
		balanceNum = Math.min(min,  balanceNum);
		System.out.println(totalBeads - n*balanceNum);

	}

}