$P2299 Mzc和体委的争夺战$

\(problem\)

#ifdef Dubug#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
inline LL In() { LL res(0),f(1); register char c ;
while(isspace(c=getchar())) ; c == '-'? f = -1 , c = getchar() : 0 ;
while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;
return res * f ;
}int n , m ;const int N = 2500 + 5 ;
const int M = 200000 + 5 ;
const int Inf = INT_MAX ;
struct node {
int v,w;
int nxt ;
};int cnt(0) ;
node edge[M<<1] ;
int head[N] ;
int dis[N] ;inline void Add(int u,int v,int w) {
edge[++cnt].v = v ;
edge[cnt].w = w ;
edge[cnt].nxt = head[u] ;
head[u] = cnt ;
return ;
}bool vis[N] ;
queue< int > q;inline void Spfa(){
    for(register int i=1;i<=n;i++) dis[i] = Inf , vis[i] = 0 ;
    q.push(1) , dis[1] = 0 , vis[1] = 1 ;
    while(!q.empty()){
        int u=q.front() ;
        q.pop() , vis[u] = 0 ;
        for(register int i=head[u];i;i=edge[i].nxt){
            int v = edge[i].v;
            if(dis[v]>dis[u]+edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                if(!vis[v]) vis[v] = 1 , q.push(v) ;
            }
        }
    }
    return ;
}
signed main() {
n = In() ; m = In() ;
for(register int i=1;i<=m;i++) {
int u , v , w ;
u = In() , v = In() , w = In() ;
Add(u,v,w) , Add(v,u,w) ;
}
Spfa() ;
cout << dis[n] << endl ;
return 0 ;
}