時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 187 解決: 51
題目描述
羅老師被邀請(qǐng)參加一個(gè)舞會(huì)，是在城市n，而羅老師當(dāng)前所處的城市為1,附近還有很多城市2~n-1，有些城市之間沒有直接相連的路，有些城市之間有直接相連的路，這些路都是雙向的，當(dāng)然也可能有多條。
現(xiàn)在給出直接相鄰城市的路長度，羅老師想知道從城市1到城市n，最短多少距離。
輸入格式
輸入n, m，表示n個(gè)城市和m條路;
接下來m行，每行a b c， 表示城市a與城市b有長度為c的路。
輸出格式
輸出1到n的最短路。如果1到達(dá)不了n，就輸出-1。
樣例輸入
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
提示
【數(shù)據(jù)規(guī)模和約定】
1≤n≤2000
1≤m≤10000
0≤c≤10000
標(biāo)簽