#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define INF 0xfffffff

#define N 1002

int n, m, G[N][N], vis[N], dist[N];

void IN()

{

    memset(vis, 0, sizeof(vis));

    for(int i=1; i<=n; i++)

    {

        dist[i]=INF;

        for(int j=1; j<=i; j++)

        {

            G[i][j]=G[j][i]=INF;

        }

    }

}

void  DIST(int S, int E)

{

    dist[S]=0;

    for(int i=1; i<=n; i++)

    {

        int index=1, MIN=INF;

        for(int j=1; j<=n; j++)

        {

            if(vis[j]==0 && dist[j]<MIN)

                MIN=dist[j], index=j;

        }

        vis[index]=1;

        for(int j=1; j<=n; j++)

        {

            if(vis[j]==0 && G[index][j]+dist[index]<dist[j])

            {

                dist[j]=G[index][j]+dist[index];

            }

        }

    }

    cout << dist[E] << endl;

}

int main()

{

    while(scanf("%d%d", &m, &n)!=EOF)

    {

        int i, a, b, c;

        IN();

        for(i=0; i<m; i++)

        {

            scanf("%d%d%d", &a, &b, &c);

            G[a][b]=G[b][a]=min(G[a][b], c);

        }

        DIST(1, n);

    }

    return 0;

}