import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;
 public class Main {
    static int[] dis;
    static int[] dis2;
    public static void main(String[] args) throws IOException {
        Reader.init( System.in );
         final int INF = Integer.MAX_VALUE/3;
        Vector<Vector<edge>> G = new Vector<Vector<edge>>();
        PriorityQueue<P> pq = new PriorityQueue<P>(100020, new Comparator<P>() {
            @Override
            public int compare(P o1, P o2) {
                return o1.dis - o2.dis;
            }
        });
        Vector<edge> tv;
        int N = Reader.nextInt();
        int R = Reader.nextInt();
        dis = new int[N];
        dis2 = new int[N];
         //init
        for (int i = 0; i < N; i++) {
            tv = new Vector<edge>();
            G.add(tv);
            dis[i] = INF;
            dis2[i] = INF;
        }
        for (int i = 0; i < R; i++) {
            edge temp = new edge();
            int a = Reader.nextInt() - 1;
            int b = Reader.nextInt() - 1;
            int d = Reader.nextInt();
            temp.cost = d;
            temp.to = b;
            tv = G.get(a);
            tv.add(temp);
             temp = new edge();
            temp.cost = d;
            temp.to = a;
            tv = G.get(b);
            tv.add(temp);
        }
         //dijkstra
        {
            dis[0] = 0;
            P tp = new P();
            pq.add(tp);
             while (!pq.isEmpty()) {
                tp = pq.poll();
                tv = G.get(tp.id);
                if (dis2[tp.id] < tp.dis) continue;//pruning
                for (int i = 0; i < tv.size(); i++) {
                    int d2 = tp.dis + tv.get(i).cost;
                    int to = tv.get(i).to;
                    if (dis[to] > d2) {
                        //swap, use swapping to avoid the missing of dis[to], it can be the value of dis2 later.
                        int temp = dis[to];
                        dis[to] = d2;
                        d2 = temp;
                        pq.add(new P(dis[to], to));
                    }
                    if (dis2[to] > d2 && d2 != dis[to]) {
                        dis2[to] = d2;
                        pq.add(new P(dis2[to], to));
                    }
                }
            }
        }
        System.out.print(dis2[N - 1]);
    }
}
 class P {
    int dis, id;
     public P(int x, int y) {
        dis = x;
        id = y;
    }
    public P(){};
}
class edge {
    int to, cost;
}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
}