ソースコード
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <list>
#include <stack>
#include <set>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
ll inf = 1e9;
ll n, m;
vector<P>g[100010];
ll jk(ll s, ll t) {
priority_queue<P, vector<P>, greater<P>>que;
ll d[100010], dis, v, nv, nc;
for (int i = 0; i < 100010; i++)d[i] = inf;
d[s] = 0;
que.push(P(0, s));
while (!que.empty()) {
dis = que.top().first;
v = que.top().second;
que.pop();
for (int i = 0; i < g[v].size(); i++) {
nv = g[v][i].first;
nc = g[v][i].second;
if (d[v] + nc<d[nv]) {
d[nv] = d[v] + nc;
que.push(P(d[nv], nv));
}
}
}
if (d[t] == inf)return -1;
else return d[t];
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m;
ll a, b, c;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c;
a--, b--;
g[a].push_back(P(b, c));
g[b].push_back(P(a, c));
}
cout << jk(0, n - 1) << endl;
return 0;
}