#include <cstdio>#include <iostream>#include <stdlib.h>#include <memory.h>using namespace std;const int maxn=1005;const int inf=1<< 30;int s[maxn][maxn],dis[maxn],visit[maxn],n,m;void dijstra(){    memset(visit,0,sizeof(visit));    for(int i=1;i<=n;i++)    dis[i]=inf;    for(int i=1;i<=n;i++)    dis[i]=s[1][i];    for(int j=1;j<=n;j++)    {        int t=-1;        for(int i=1;i<=n;i++)        {            if(!visit[i] && (dis[i]<dis[t]||t==-1) )            t=i;        }        visit[t]=1;        for(int i=1;i<=n;i++)        {            if(!visit[i] && s[i][t] && dis[i]>dis[t]+s[t][i])            dis[i]=dis[t]+s[t][i];        }    }}int main(){    //freopen("in.txt","r",stdin);    scanf("%d%d",&m,&n);    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++)    s[i][j]=inf;    for(int i=1;i<=n;i++)    s[i][i]=0;    for(int i=1;i<=m;i++)    {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        if(c<s[a][b])        s[a][b]=s[b][a]=c;    }    dijstra();//    int ans=-1;//    for(int i=1;i<=n;i++)//    {//        if(ans==-1 || dis[i]>ans)//        ans=dis[i];//    }    printf("%d",dis[n]);    return 0;}