Description

在一个nXn的网格图上，放置着m个礼物，每个礼物有一个价值v_i(1<=i<=m)，你可以选择一个礼物，然后选择：

（1）取走与它同列的所有礼物，或者

（2）取走与它同行的所有礼物

请问所能获取的礼物的最大价值之和是多少？

Input Format

第一行两个整数n，m。

之后m行，每行三个整数x_i，y_i，v_i，表示第i个礼物在第x_i行，第y_i列的格子上(不同礼物可能会在同一个格子)，其价值为v_i。

Output Format

一个整数，表示能获取的最大的礼物价值之和。

6 7
1 3 1
2 2 2
2 4 4
3 3 6
3 6 3
5 2 5
5 4 6

11

Hint

【样例解释】

		1
	2		4
		6			3
	5		6

选择第5行的任意一个礼物，然后将第5行取完

【数据范围】

对于40%的数据，1≤n,m≤100

对于70%的数据，1≤n,m≤1000，0<v_i≤10000

对于100%的数据，1≤n≤1000，1≤m≤10⁵，1≤x_i,y_i≤n，v_i≤10⁶

Source

余姚竞赛2021