#include #ifdef DEBUG #include #else #define dump(...) ((void)0) #endif template bool chmin(T &a, const U &b){ return (a > b ? a = b, true : false); } template bool chmax(T &a, const U &b){ return (a < b ? a = b, true : false); } template void fill_array(T (&a)[N], const U &v){ std::fill((U*)a, (U*)(a + N), v); } template auto make_vector(const std::array &a, T value = T()){ static_assert(I >= 1); static_assert(N >= 1); if constexpr (I == 1){ return std::vector(a[N - I], value); }else{ return std::vector(a[N - I], make_vector(a, value)); } } template std::ostream& operator<<(std::ostream &s, const std::vector &a){ for(auto it = a.begin(); it != a.end(); ++it){ if(it != a.begin()) s << " "; s << *it; } return s; } template std::istream& operator>>(std::istream &s, std::vector &a){ for(auto &x : a) s >> x; return s; } std::string YesNo(bool value){return value ? "Yes" : "No";} std::string YESNO(bool value){return value ? "YES" : "NO";} std::string yesno(bool value){return value ? "yes" : "no";} template void putl(const T &value){ std::cout << value << "\n"; } template void putl(const Head head, const Tail &... tail){ std::cout << head << " "; putl(tail ...); } namespace haar_lib { template struct edge { int from, to; T cost; int index = -1; edge(){} edge(int from, int to, T cost): from(from), to(to), cost(cost){} edge(int from, int to, T cost, int index): from(from), to(to), cost(cost), index(index){} }; template struct graph { using weight_type = T; using edge_type = edge; std::vector>> data; auto& operator[](size_t i){return data[i];} const auto& operator[](size_t i) const {return data[i];} auto begin() const {return data.begin();} auto end() const {return data.end();} graph(){} graph(int N): data(N){} bool empty() const {return data.empty();} int size() const {return data.size();} void add_edge(int i, int j, T w, int index = -1){ data[i].emplace_back(i, j, w, index); } void add_undirected(int i, int j, T w, int index = -1){ add_edge(i, j, w, index); add_edge(j, i, w, index); } template void read(int M){ for(int i = 0; i < M; ++i){ int u, v; std::cin >> u >> v; u -= I; v -= I; T w = 1; if(WEIGHTED) std::cin >> w; if(DIRECTED) add_edge(u, v, w, i); else add_undirected(u, v, w, i); } } }; template using tree = graph; } namespace haar_lib { template auto dijkstra(const graph &graph, std::vector src){ using P = std::pair; const int n = graph.size(); std::vector> dist(n); std::vector check(n, false); std::priority_queue, std::greater

> pq; for(auto s : src){ dist[s] = 0; pq.emplace(0, s); } while(not pq.empty()){ const auto [d, i] = pq.top(); pq.pop(); if(check[i]) continue; check[i] = true; for(auto &e : graph[i]){ if(not dist[e.to]){ dist[e.to] = d + e.cost; pq.emplace(*dist[e.to], e.to); }else{ if(*dist[e.to] > d + e.cost){ dist[e.to] = d + e.cost; if(not check[e.to]) pq.emplace(*dist[e.to], e.to); } } } } return dist; } } namespace haar_lib {} namespace solver { using namespace haar_lib; constexpr int m1000000007 = 1000000007; constexpr int m998244353 = 998244353; void init(){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(12); std::cerr << std::fixed << std::setprecision(12); std::cin.exceptions(std::ios_base::failbit); } const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; void solve(){ int N, M; std::cin >> N >> M; graph g(2 * N * N); auto index = make_vector({2, N, N}); { int k = 0; for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ index[0][i][j] = k++; index[1][i][j] = k++; } } } auto cost = make_vector({N, N}, 0); for(int i = 0; i < M; ++i){ int h, w, c; std::cin >> h >> w >> c; --h, --w; cost[h][w] = c; } for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ for(auto [dx, dy] : dir){ int x = i + dx; int y = j + dy; if(x < 0 or y < 0 or x >= N or y >= N) continue; g.add_edge(index[0][i][j], index[0][x][y], 1 + cost[x][y]); g.add_edge(index[1][i][j], index[1][x][y], 1 + cost[x][y]); g.add_edge(index[0][i][j], index[1][x][y], 1); } } } int64_t ans = dijkstra(g, {index[0][0][0]})[index[1][N - 1][N - 1]].value(); std::cout << ans << "\n"; } } int main(){ solver::init(); while(true){ try{ solver::solve(); std::cout << std::flush; std::cerr << std::flush; }catch(const std::istream::failure &e){ break; }catch(...){ break; } } return 0; }