#include using namespace std; using grid = vector>; vector dx{1, 0, -1, 0}, dy{0, 1, 0, -1}; int main() { int n, m; cin >> n >> m; grid board(n, vector(n, 1)); for (int i = 0; i < m; i++) { int h, w, c; cin >> h >> w >> c; board.at(h - 1).at(w - 1) += c; } vector cost(2 * n * n, 1L << 60); priority_queue> q; q.emplace(0, 0); while (not q.empty()) { auto [d, id] = q.top(); q.pop(); if (d >= cost.at(id)) continue; cost.at(id) = d; int state = id / (n * n), row = id / n % n, column = id % n; for (int i = 0; i < 4; i++) { int newrow = row + dx[i], newcolumn = column + dy[i], newid = id + n * dx[i] + dy[i]; if (newrow < 0 or n <= newrow or newcolumn < 0 or n <= newcolumn) continue; q.emplace(d + board.at(newrow).at(newcolumn), newid); if (state == 0) { q.emplace(d + 1, newid + n * n); } } } cout << cost.at(2 * n * n - 1) << endl; }