#1207. Day4E. ZJY 的幼儿园清扫惨案

魔王 ZJY 横征暴敛，作恶无数，他喜欢吃糖果，并发誓要把富有糖果的渡渡鸟幼儿园清扫干净。但见 SL 与 WYB 仍谈笑风生，SL 和 WYB 想逃脱 ZJY 可笑的声讨，并用实力继续嘲讽 ZJY。

渡渡鸟幼儿园是一栋拥有 $n \times n$ 个方格房间的方阵形迷宫，每间相邻房间之间有门可以互相通行。SL 和 WYB 最初在方阵的西北角（上北下南），位置 $(1, 1)$，但幼儿园与外界唯一的出入口，是东南角房间 $(n, n)$ 的超空间航路。每经过一扇门，SL 和 WYB 都要花费固定的时间。他们想要尽快到达出口。

另外呢，为了逗小朋友开心，幼儿园的有些房间里放着一些糖果。SL 和 WYB 经过的时候可以顺带把这个房间里的糖果全部捎走，不需要多余的时间。

他们俩想要在最短的时间内带走尽可能多的糖果，这样子 ZJY 能找到的糖果就变少了。

注：渡渡鸟幼儿园的坐标系统里，房间由坐标 $(x, y)$ 表示，$x$ 表示到从北方边界起始的标号，$y$ 表示从西方边界起始的标号。

第一行两个整数 $n,\ k$ 。

接下来 $k$ 行，每行三个正整数 $x_i,\ y_i,\ s_i$ ，表示在 $(x_i,\ y_i)$ 处有 $s_i$ 颗糖果。

保证对于任意的 $i \ne j$ 不存在 $x_i = x_j$ 且 $y_i = y_j$ 。

输出一行一个整数，表示 SL 和 WYB 能带走的最大糖果总数。

样例输入

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

$1 \le n \le 20$

$0 \le k \le n^2$

$1 \le x_i,\ y_i \le n$

$1 \le s_i \le 10^5$