# ソースコード

```
#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
using namespace std;
class gragh{
int V,E;
vector<vector<pair<int,int>>> edge; //edge[from][i] ={to,cost}
public:
//only for 0-indexed
gragh(int v,int e,int *from,int *to,int *cost){
V=v;E=e; 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);
} }
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;
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 bellmanFord(){
}
};
int main(){
int n, m; cin>>n>>m;
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);
int ans=g.dijkstra(0, n-1);
if(ans==inf) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
```