#include <vector>
#include <queue>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
int N, M;
vector<pair<int,long>>G[505*505*2];
long A[505][505];
long dp[505*505*2];
int main() {
	cin >> N >> M;
	rep(i, M) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		A[a][b] = c;
	}
	const int dx[] = {1, 0, -1, 0, 1};
	rep(i, N) rep(j, N) {
		rep(r, 4) {
			int ni = i + dx[r], nj = j + dx[r + 1];
			if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
			long cost = 1 + A[i][j];
			int a = i * N + j, b = ni * N + nj;
			G[b].push_back({a, cost});
			G[b].push_back({a + N*N, 1});
			G[b + N*N].push_back({a + N*N, cost});
		}
	}
	using S = pair<long, int>;
	priority_queue<S, vector<S>, greater<S>> pq;
	pq.push({0, 0});
	rep(i, N * N * 2) dp[i] = 1e18;
	dp[0] = 0;
	while(pq.size()) {
		auto[e, v] = pq.top();pq.pop();
		if(dp[v]!=e) continue;
		for(auto[nv,cst]:G[v])if(dp[nv]>dp[v]+cst)dp[nv]=dp[v]+cst,pq.push({dp[nv],nv});
	}
	cout<<dp[2*N*N-1]<<endl;
}