#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int N, M;
LL D[500][500];
LL dp[500][500][2];

struct QueueNode {
	int x, y, t;
	LL d;
};

bool operator<(QueueNode l, QueueNode r) { return l.d > r.d; }

int main() {
	cin >> N >> M;
	rep(i, N) rep(j, N) D[i][j] = 1; D[0][0] = 0;
	rep(i, M) {
		int y, x, c; cin >> y >> x >> c; y--; x--;
		D[x][y] += c;
	}

	rep(i, N) rep(j, N) rep(t, 2) dp[i][j][t] = -1;

	priority_queue<QueueNode> G;
	G.push({ N - 1,N - 1,0,0 });
	G.push({ N - 1,N - 1,1,0 });

	const int dx[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

	while (G.size()) {
		int x = G.top().x;
		int y = G.top().y;
		int t = G.top().t;
		LL d = G.top().d;
		G.pop();

		if (x < 0 || x >= N) continue;
		if (y < 0 || y >= N) continue;
		if (dp[x][y][t] != -1) continue;

		dp[x][y][t] = d;

		rep(di, 4) {
			G.push({ x + dx[di][0], y + dx[di][1], t, d + D[x][y] });
		}

		if (t < 1) {
			rep(di, 4) {
				G.push({ x + dx[di][0], y + dx[di][1], t + 1, d + 1 });
			}
		}
	}

	LL ans = min(dp[0][0][0], dp[0][0][1]);
	cout << ans << endl;

	return 0;
}