题目描述

在一个 n× n 的网格图上，放置着 m 个礼物，每个礼物有一个价值 v_i (1≤i≤m)，
你可以选择一个礼物，然后选择：
（1）取走与它同列的所有礼物， 或者（2）取走与它同行的所有礼物
请问所能获取的礼物的最大价值之和是多少？

输入格式

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

输出格式

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

样例数据

input

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

output

11

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

【数据范围】

对于 40%的数据， 1≤n,m≤100
对于 70%的数据， 1≤n,m≤1000， 0<v_i≤10000
对于 100%的数据， 1≤n≤1000， 1≤m≤10^5， 1≤x_i,y_i≤n， v_i≤10^6