#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是頂點(diǎn)的編號(hào)
int V, dist[maxn];
vector<P> G[maxn];
void dijkstra(
int s) {
//通過(guò)指定greater<P>參數(shù)，堆按照f(shuō)irst從小到大的順序取出值
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;
}