給定一個?n 個點?m 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。
請你求出?11?號點到?n?號點的最短距離，如果無法從?1?號點走到?n?號點，則輸出??1。
輸入格式
第一行包含整數?n?和?m。
接下來?m?行每行包含三個整數?x,y,z，表示存在一條從點?x?到點?y 的有向邊，邊長為?z。
輸出格式
輸出一個整數，表示?1?號點到?n?號點的最短距離。
如果路徑不存在，則輸出??1。
數據范圍
1≤n≤500
1≤m≤10^5
圖中涉及邊長均不超過10000。
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3?
#include<stdio.h>
#include<string.h>
int state[100005];
int dis[100005];
int e[100005];
int ne[100005];
int head[100005];
int w[100005];
int idx=1;
int n,m;
int min(int a,int b) {if(a<b)return a;else {return b;}
}
void dijsktra() {dis[1]=0;for(int i=1; i<=n; i++) {int t=-1;for(int j=1; j<=n; j++) {if(!state[t]&&(t==-1||dis[t]>dis[j])) {t=j;}}state[t]=1;for(int u=head[t]; u!=-1; u=ne[u]) {int j=e[u];dis[j]=min(dis[j],dis[t]+w[u]);}}
}
void addedge(int a,int b,int c) {e[idx]=b;w[idx]=c;ne[idx]=head[a];head[a]=idx++;}
int main() {memset(dis,0x3f,sizeof(dis));memset(head,-1,sizeof(head));scanf("%d",&n);scanf("%d",&m);for(int i=1; i<=m; i++) {int u,v,w;scanf("%d",&u);scanf("%d",&v);scanf("%d",&w);addedge(u,v,w);}if (dis[m] == 0x3f3f3f) printf("-1");else {printf("%d",dis[m]);}
}
