Super Marble

MedalPluS and his friend NOIRP have discovered an epic game called Super Marble. The game is played on an \(n \times n\) grid that contains several enemies. Each enemy occupies a distinct cell and carries a score. When you place your marble in an empty cell (i.e. a cell without any enemy), your marble destroys all enemies in the same row and column, and you earn a score equal to the sum of their scores.

Your task is to choose an empty cell to maximize the total score obtained by destroying the enemies in its row and column.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the size of the grid and the number of enemies respectively.

Each of the next \(m\) lines contains three integers \(r\), \(c\), and \(s\) indicating that there is an enemy at row \(r\) and column \(c\) with score \(s\). It is guaranteed that no two enemies share the same position, and \(1 \le r, c \le n\).

outputFormat

Output a single integer: the maximum score that can be achieved by selecting an appropriate empty cell.

sample

3 2
1 2 5
2 3 10

15