この問題は最短経路問題そのものです。よってダイクストラ法を用いることで \(O(M\log N)\) で答えを求めることができます。

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 a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].push_back({b,c});
    G[b].push_back({a,c});
  }

  const long long INF = (long long)1e18;
  vector<long long> dist(n, INF);
  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(d != dist[v]){
      continue;
    }
    for(auto[vv, cc]: G[v]){
      if(dist[v] + cc < dist[vv]){
        dist[vv] = dist[v] + cc;
        q.push({-dist[vv], vv});
      }
    }
  }

  if(dist[n-1] == INF){
    cout << -1 << endl;
  }else{
    cout << dist[n-1] << endl;
  }
}

実装例 (Python)

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

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

if dist[-1] == INF:
  print(-1)
else:
  print(dist[-1])