#include using namespace std; int main() { ios::sync_with_stdio(false); int N, M; { cin >> N >> M; } vector> C(N, vector(N)); { for (int i = 0; i < M; ++i) { int H, W, _C; cin >> H >> W >> _C; C[H - 1][W - 1] = _C; } } const int64_t INF = (int64_t) 1 << 60; vector>> dis(N, vector>(N, vector(2, INF))); { set> bag; bag.emplace(dis[0][0][0] = 0, 0, 0, 0); while (bag.size()) { int64_t d; int x, y, t; tie(d, x, y, t) = *bag.begin(); bag.erase(bag.begin()); if (d != dis[x][y][t]) continue; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; for (int _ = 0; _ < 4; ++_) { int nx = x + dx[_]; int ny = y + dy[_]; if (nx < 0 || nx == N || ny < 0 || ny == N) continue; if (d + 1 + C[nx][ny] < dis[nx][ny][t]) { bag.emplace(dis[nx][ny][t] = d + 1 + C[nx][ny], nx, ny, t); } if (t == 0 && d + 1 < dis[nx][ny][1]) { bag.emplace(dis[nx][ny][1] = d + 1, nx, ny, 1); } } } } int res = min(dis[N - 1][N - 1][0], dis[N - 1][N - 1][1]); cout << res << endl; }