学步园

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7fffffff
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct edge{
	int to,next,v;
}e[40001];
int n,m,cnt,head[10001],dis[10001];
void ins(int u,int v,int w){
	e[++cnt]=(edge){v,head[u],w};head[u]=cnt;
	e[++cnt]=(edge){u,head[v],w};head[v]=cnt;
}
void spfa() {  
    int q[10001], t = 0, w = 0;  
    bool inq[10001];  
    memset(inq, 0, sizeof (inq));  
    memset(dis, 127, sizeof (dis));  
    dis[1]=0;q[0]=1;inq[1]=1;  
    while (t <= w) {  
        int now = q[t++];
        for (int i = head[now]; i; i = e[i].next) {  
            if (dis[now] + e[i].v < dis[e[i].to]) {  
                dis[e[i].to] = dis[now] + e[i].v;  
                if (!inq[e[i].to]) {  
                    q[++w] = e[i].to;  
                    inq[e[i].to] = 1;  
                }  
            }  
        }  
        inq[now] = 0;  
    }  
}  
int main(){
	m=read();n=read();
	for(int i=1;i<=m;i++){
		int a=read(),b=read(),c=read();
		ins(a,b,c);
	}
	spfa();
	printf("%d",dis[n]);
	return 0;
}