#include<bits/stdc++.h> using namespace std; #define int long long struct Edge{int v, c;}; #define pii pair<long long , int> signed main(){ int n , m; cin>>n>>m; vector<vector<Edge>> rev_g(n+1); vector<vector<int>> cost(n+1); for(int i = 0 ; i< m ;i++){ int u , v , c; cin>>u>>v>>c; rev_g[v].push_back({u , c}); cost[u].push_back(c); } for(int i = 1; i<=n;i++){ sort(cost[i].begin() , cost[i].end()); } priority_queue<pii , vector<pii>, greater<pii>> pq; pq.push({0 , n}); vector<int> dist(n + 1, LLONG_MAX/4) , seen(n+1); dist[n]=0; while(!pq.empty()){ int d = pq.top().first; int u = pq.top().second; pq.pop(); if(d != dist[u])continue; for(auto v : rev_g[u]){ seen[v.v]++; int k = cost[v.v].size(); int cand = dist[u] + cost[v.v][k - seen[v.v]]; if(cand < dist[v.v]){ dist[v.v] = cand; pq.push({dist[v.v] , v.v}); } } } cout<<dist[1]; }