poj 2387
2387

/*#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 2100 , M = N * 2 , INF = 1e8 ;
int n,t ;
int h[N],e[M],w[M],ne[M],idx ;
int dist[N] ;
int q[N] ;
bool st[N] ;

void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a] , h[a] = idx++;
}

void spfa(){
    for(int i = 1 ; i <= n ; i++) dist[i] = INF ;
    dist[1] = 0 ;
    int hh = 0 , tt = 0 ;
    q[tt++] = 1 ,st[1] = 1;
    while(hh != tt){
        int t = q[hh++] ;
        st[t] = 0 ;
        if(hh == n) hh = 0 ;
        for(int i =  h[t] ; ~i ; i = ne[i]){
            int j = e[i] ;
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i] ;
                if(!st[j]){
                    st[j] = 1;
                    q[tt++] = j ;
                    if(tt == n) tt = 0 ;
                }
            }
        }
    }
}

int main()
{
    cin >> t >> n ;
    memset(h,-1,sizeof h) ;
    for(int i = 0 ; i < t ; i++){
        int a,b,c;
        cin >> a>> b >> c ;
        add(a,b,c),add(b,a,c) ;
    }

    spfa() ;

    cout << dist[n] << endl;
    return 0;
}*/
/*#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std ;
typedef pair<int,int> pii ;
const int N = 2100 , M = 2 * N , INF = 1e8 ;
int t,n ;
int h[N],e[M],ne[M],w[M],idx ;
int dist[N] ;
bool st[N] ;

void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a] , h[a] = idx++ ;
}

void dijkstra(){
    for(int i = 1 ; i <= n ; i++) dist[i] = INF ;
    dist[1] = 0 ;

    priority_queue<pii,vector<pii>,greater<pii> > heap ;
    heap.push({0,1}) ;  //第一个数代表距离，第二个数代表编号 ;

    while(heap.size() ){
        pii t = heap.top() ;
        heap.pop() ;
        int ver = t.second , distance = t.first ;
        if(st[ver]) continue ;
        st[ver] = 1 ;
        for(int i = h[ver] ; ~i ; i = ne[i]){
            int j = e[i] ;
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i] ;
                heap.push({dist[j],j}) ;
            }
        }

    }
}

int main(){
    cin >> t >> n ;
    memset(h,-1,sizeof h) ;
    for(int i = 0 ; i < t ; i++){
        int a,b,c;
        cin >> a>> b>> c ;
        add(a,b,c) , add(b,a,c) ;
    }

    dijkstra() ;

    cout << dist[n] << endl ;

    return 0 ;
}*/

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <iostream>

using namespace std ;
const int N = 2100 , M = 2 * N , INF = 1e8 ;

int t,n ;
int g[N][N] ,dist[N] ;
bool st[N] ;

void dijkstra(){
    for(int i = 1 ; i <= n ; i++) dist[i] = INF ;
    dist[1] = 0 ;

    for(int i = 0 ; i < n ; i++){
        int id ,mind = INF ;
        for(int j = 1 ; j <= n ; j++){
            if(!st[j] &&dist[j] < mind){
                mind = dist[j] ;
                id = j ;
            }
        }
        st[id] = 1 ;
        for(int j = 1 ; j <= n ; j++) dist[j] = min(dist[j],dist[id] + g[id][j]) ;
    }
}

int main(){
    cin >> t >> n ;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= n ; j++){
            g[i][j] = INF;
            if(i == j) g[i][j] = 0 ;
        }
    }

    for(int i = 0 ; i < t ; i++){
        int a,b,c ;
        cin >>a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b],c) ;
    }

    dijkstra() ;

    cout << dist[n] << endl ;
    return 0 ;
}