public static void main(String[] args){
		
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int m = in.nextInt();
		
		HashMap<Integer, HashMap<Integer, Integer>> g = new HashMap<Integer, HashMap<Integer, Integer>>();
		int[] dist = new int[n+1];
		for(int i=1;i<=n;i++){
			dist[i]=Integer.MAX_VALUE;
			g.put(i, new HashMap<Integer, Integer>());
		}
		for(int i=0;i<m;i++){
			int a = in.nextInt();
			int b = in.nextInt();
			int edge = in.nextInt();
			g.get(a).put(b, edge);
		}
		
		new Dijkstra().dijkstra(4, dist, g);
		for(int i=1;i<=n;i++){
			System.out.printf("Node %d has shortest distance %d\n", i, dist[i]);
		}
	}