题目描述

罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。

现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。

输入格式

输入n, m，表示n个城市和m条路;

接下来m行，每行a b c， 表示城市a与城市b有长度为c的路。

输出格式

输出1到n的最短路。如果1到达不了n，就输出-1。

样例

样例输入

复制5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出

复制90

数据范围与提示

【数据规模和约定】

1≤n≤2000

1≤m≤10000

0≤c≤10000

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
struct node{
	int x;
	int y;
	int w;
}a[1000005];
int dist[1000005];
int n,m;
bool flag; 
int f(int q,int p){
	memset(dist,0x3f3f3f3f,sizeof(dist));
	dist[q]=0;
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=m*2;j++){
			if(dist[a[j].y]>dist[a[j].x]+a[j].w){
			    dist[a[j].y]=dist[a[j].x]+a[j].w;
		    }
		}
	}
	for(int j=1;j<=m*2;j++){
		if(dist[a[j].y]>dist[a[j].x]+a[j].w){
		    flag=true;
		}
	}
	return dist[p];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].w;
		a[i+m].x=a[i].y,a[i+m].y=a[i].x,a[i+m].w=a[i].w;
	}
	int t=f(1,n);
    if(t==0x3f3f3f3f)cout<<"-1";  
    else cout<<t<<endl;
	
	return 0;
}