import java.util.*;

//Floyd基于邻接矩阵

public class Floyd模板 {
	static int N = 1005;
	static int[][] G = new int[N][N];
	
	static int n, m;
	static void init() {
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < N; j++){
				G[i][j] = 0x3f3f3f3f;
			}
		}
	}
	public static void main(String[] args) {
		init();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		int u, v, w;
		while (m-- > 0) {
			u = sc.nextInt();
			v = sc.nextInt();
			w = sc.nextInt();
			G[u][v] = G[v][u] = w;
		}
	 
		floyd();
		System.out.println(G[1][n]);
	}
	
	static void floyd() {
		  for (int k = 1; k <= n; k++) {
		        for (int i = 1; i <= n; i++) {
		            for (int j = 1; j <= n; j++) {
		          		G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
		            }
		        }
		    }
	}
	static int min(int a, int b) {
		return a > b ? b : a;
	}
}