#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;

typedef pair<int, int> P; //first是最短距离，second是顶点的编号
int V, dist[maxn];
vector<P> G[maxn];

void dijkstra(int s) {
    //通过指定greater<P>参数，堆按照first从小到大的顺序取出值
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist + V , INF);
    dist[s] = 0;
    while(!que.empty()) que.pop();
    que.push(P(0, s));
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int u = p.second;
        if(dist[u] < p.first) continue;
        int sz = G[u].size();
        for(int i=0;i<sz;i++) {
            int to = G[u][i].second;
            int cost = G[u][i].first;
            if(dist[to] > dist[u] + cost) {
                dist[to] = dist[u] + cost;
                que.push(P(dist[to], to));
            }
        }
    }
}

int main() {
    int m;
    scanf("%d%d" , &m, &V);
    for(int i=0;i<V;i++) G[i].clear();
    for(int i=0;i<m;i++) {
        int from, to, cost;
        scanf("%d%d%d" , &from, &to, &cost);
        from --; to --;
        G[from].push_back(P(cost, to));
        G[to].push_back(P(cost, from));
    }
    dijkstra(0);
    printf("%d\n", dist[V-1]);
    return 0;
}