题目描述

设有 n * n 的方格图，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）: 禾木从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格数变为 0）。 禾木要从从 A 点到 B 点共走两次，请你计算出禾木能够取得的数最大总和是多少。

输入格式

第 1 行包含两个正整数 n，m，n 表示方格的大小, m 表示填入正整数的个数。

第 2 行到第 m + 1 行，每行包含 3 个正整数 x, y, z，x 和 y 分别表示行和列，z 表示该位置上所放的数。

输出格式

1行，包含一个整数，表示禾木能够取得的最大整数和。

样例1

8 8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14

67

样例2

4 5
1 1 13
2 2 6
3 4 7
3 2 5
4 1 14

45

数据范围

2 ≤ n ≤ 9； 1 ≤ m ≤ n * n； 1 ≤ x, y ≤ n; 1 ≤ z ≤ 1000;