ソースコード
#include <bits/stdc++.h>
#define inf 1000000000
#define mod 1000000007
using namespace std;
using LL = long long;
struct gragh{
int V,E;
std::vector<std::vector<std::pair<int,int>>> edge; //edge[from][i] ={to,cost}
//only for 0-indexed
gragh(int v,int e,int *from,int *to,int *cost){
V=v;E=e; std::pair<int,int>p;
for(int i=0;i<e;i++){
//if(edge.size()<=from[i])edge.resize(from[i]+1);
edge.resize(v);
p.first=to[i]; p.second=cost[i]; edge[from[i]].push_back(p);
p.first=from[i]; p.second=cost[i]; edge[to[i]].push_back(p);
} }
gragh(int v,int e,std::vector<int> &from,std::vector<int> &to,std::vector<int> &cost){
V=v;E=e; std::pair<int,int>p;
for(int i=0;i<e;i++){
//if(edge.size()<=from[i])edge.resize(from[i]+1);
edge.resize(v);
p.first=to[i]; p.second=cost[i]; edge[from[i]].push_back(p);
p.first=from[i]; p.second=cost[i]; edge[to[i]].push_back(p);
} }
int dijkstra(int start,int goal){
int done[V]; for(int i=0;i<V;i++)done[i]=0; done[start]=1;
int vertex[V]; for(int i=0;i<V;i++)vertex[i]=inf; vertex[start]=0;
std::queue<int> que; que.push(start);
int from, to, cost;
while(que.size()!=0){
from=que.front();
for(int i=0; i<edge[from].size(); i++){
to=edge[from][i].first; cost=edge[from][i].second;
if( vertex[to]>vertex[from]+cost){
vertex[to]=vertex[from]+cost;
que.push(to);
}
}
que.pop();
}
return vertex[goal]; }
};
int main(){
int n,m;cin>>n>>m;
vector<int> a(m),b(m),c(m);
for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>c[i];
for(int i=0;i<m;i++){a[i]--;b[i]--;}
gragh G(n,m,a,b,c);
cout<<(G.dijkstra(0,n-1)!=inf?G.dijkstra(0,n-1):-1)<<endl;
}