この問題は地点 \(1\) から地点 \(N\) までの最短距離を求める問題であり、ダイクストラ法そのものを用いてとくことができます。

計算量は \(O(N+M\log M)\) です。

なお、C++の priority_queue はデフォルトでは値が大きなものから順に取り出すことに注意してください。

適切な実装により値が小さなものから順に取り出すこともできますが、以下の実装例では値を -1 倍してキューに挿入することで、デフォルトのまま実質的に値が小さなものから順に取り出せるようにしています。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int,int>>>G(n);
  for(int i=0; i<m; i++){
    int u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    G[u].push_back({v, c});
  }

  vector<long long>dist(n, 1e18);
  dist[0] = 0;
  priority_queue<pair<long long,int>>q;
  q.push({0, 0});
  while(q.size() > 0){
    auto[d, v] = q.top(); q.pop();
    d = -d;
    if(dist[v] != d){
      continue;
    }
    for(auto[vv, cc]: G[v]){
      if(dist[vv] > dist[v] + cc){
        dist[vv] = dist[v] + cc;
        q.push({-dist[vv], vv});
      }
    }
  }
  cout << dist[n-1] << endl;
}

python の heapq はデフォルトで値が小さなものから順に取り出します。

実装例 (Python)

import heapq
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
  u, v, c = map(int, input().split())
  u -= 1
  v -= 1
  G[u].append((v, c))

dist = [10**18] * N
dist[0] = 0
q = [(0,0)]
while len(q) > 0:
  d, v = heapq.heappop(q)
  if dist[v] != d:
    continue
  for vv, cc in G[v]:
    if dist[vv] > dist[v] + cc:
      dist[vv] = dist[v] + cc
      heapq.heappush(q, (dist[vv], vv))

print(dist[-1])