# ソースコード

```
#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);
while(que.size()!=0){
for(int i=0;i<edge[que.front()].size();i++){
if( vertex[ edge[que.front()][i].first() ] > vertex[que.front()] + edge[que.front()][i].second() ){
vertex[edge[que.front()][i].first()] = vertex[que.front()] + edge[que.front()][i].second();
que.push(edge[que.front()][i].first());
}
}
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];
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;
}
```