A - Til the Cows Come Home

给定一个 �(�≤1000)n(n≤1000) 个点，�(�≤2000)m(m≤2000) 条边的图，求从节点 11 到节点 �n 的最短路。

Input

第一行两个整数 �,�m,n。 接下来 �m 行，每行三个整数 �,�,�u,v,w，表示 �u 到 �v 和 �v 到 �u 都有一条权值为 �w 的边。

Output

一行一个整数表示答案。

Sample

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

90

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e3+10;
int dist[N];
int g[N][N];
bool st[N];
int n,m;
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=1;j<=n;j++){
            if(st[j]==0&&(t==0||dist[t]>dist[j]))
            t=j;
        }
        st[t]=1;
        for(int j=1;j<=n;j++)
        dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return;
    else
    cout<<dist[n]<<endl;
}

int main(){
    cin>>m>>n;
    memset(g,0x3f,sizeof(g));
    while(m--){
        int x,y,w;
        cin>>x>>y>>w;
        g[x][y]=g[y][x]=min(g[x][y],w);
    }
    dijkstra();
    return 0;
}