#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define MAXN 5050
int head[MAXN],to[MAXN],nex[MAXN],val[MAXN],tot;
int t,n;
int f[MAXN],v[MAXN];
void add(int x,int y,int z)
{
    to[++tot]=y;
    val[tot]=z;
    nex[tot]=head[x];
    head[x]=tot;
}
void dijkstra()
{
    int temp,k,y;
    memset(f,0x3f,sizeof(f));
    memset(v,0,sizeof(v));
    f[1]=0;
    for(int i=1;i<=n;i++)
    {
        temp=1<<30;
        for(int j=1;j<=n;j++)
            if(v[j]==0&&f[j]<temp)
            {
                temp=f[j];
                k=j;
            }
        v[k]=1;
        for(int j=head[k];j;j=nex[j])
        {
            y=to[j];
            if(f[y]>f[k]+val[j]) f[y]=f[k]+val[j];
        }
    }
}
int main()
{
    cin>>t>>n;
    for(int i=1;i<=t;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra();
    cout<<f[n]<<endl;
    return 0;
}