#include using namespace std; #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define All(v) (v).begin(), (v).end() #define pb push_back #define MP(a, b) make_pair((a), (b)) template vector make_vec(size_t a, T val) { return vector(a, val); } template auto make_vec(size_t a, Ts... ts) { return vector(a, make_vec(ts...)); } using ll = long long; using pii = pair; using pll = pair; using Graph = vector>; template struct edge { int to; T cost; edge(int t, T c) : to(t), cost(c) {} }; template using WGraph = vector>>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; const int dx[] = {0, -1, 0, 1}; const int dy[] = {1, 0, -1, 0}; int main() { int N, M; cin >> N >> M; auto dist = make_vec(N, N, 2, LINF); auto check = make_vec(N, N, 0LL); rep(i, M) { ll h, w, c; cin >> h >> w >> c; h--, w--; check[h][w] = c; } using State = pair>; priority_queue, greater> que; que.push({0LL, {{0, 0}, 0}}); dist[0][0][0] = 0; while(!que.empty()) { auto [cost, pp] = que.top(); que.pop(); auto [p, skipped] = pp; auto [x, y] = p; rep(i, 4) { int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; if(skipped == 0) { if(check[ny][nx] && (dist[ny][nx][0] > cost + 1)) { dist[ny][nx][1] = cost + 1 + check[ny][nx]; que.push({cost + 1, {{nx, ny}, 1}}); } } if(dist[ny][nx][skipped] > cost + 1 + check[ny][nx]) { dist[ny][nx][skipped] = cost + 1 + check[ny][nx]; que.push({cost + 1 + check[ny][nx], {{nx, ny}, skipped}}); } } } cout << min(dist[N - 1][N - 1][1], dist[N - 1][N - 1][0]) << endl; }