/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Dell
 */

import java.io.*;
import java.util.*;

public class DijkstraCodingNinja {
    
    public static void dijkstra(int[][] adjMatrix){
    
        int v = adjMatrix.length;
        boolean[] visited = new boolean[v];
        int[] distance = new int[v];
        
        distance[0] = 0;
        
        //setting distance of all the vertices to max value.
        for(int i = 1 ; i < v ; i++){
        
            distance[i] = Integer.MAX_VALUE;
            
        }
        
        for(int i = 0 ; i < v - 1 ; i++){
        
            //finding minimum vertex among the set of vertex
            
            int minVertex = findMinVertex(distance , visited);
            
            //setting vertex as visted.
            visited[minVertex] = true;
            
            //exploring a neigbor
            for(int j = 0 ; j < v ; j++){
            
                if(adjMatrix[minVertex][j] != 0 && !visited[j] && distance[minVertex]!= Integer.MAX_VALUE){
                
                    int newDist = distance[minVertex] + adjMatrix[minVertex][j];
                
                    if(newDist < distance[j]){
                    
                        distance[j] = newDist;
                    
                    }
                }
            
            
            }
            
            
        
        }
        
        for(int i = 0 ; i < v ; i++){
        
            System.out.println("vertex :" + i +" : Minimum distance " + distance[i]);
        
        }
        
        
    
    
    }
    
    public static int findMinVertex(int[] distance , boolean[] visited){
    
        int minVertex = -1;
        //trying to find a minimum vertex from the graph, and setting it as visited
        for(int i = 0 ; i < distance.length ; i++){
        
            if(!visited[i] && (minVertex == -1 || distance[i] < distance[minVertex])){
            
                minVertex = i;
            
            }
            
            
        
        }
    
        return minVertex;
    
    }
    
    
    
    public static void main(String[] args){
    
        Scanner sc = new Scanner(System.in);
        
        //no of vertices
        int vertices = sc.nextInt();
        //no of edges
        int edges  = sc.nextInt();
        
        int[][] adjMatrix = new int[vertices][vertices];
        
        for(int i = 0 ; i < edges ; i++){
        
        
            //the vertices of an edge
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
        
            //the weight of that edge
            int weight = sc.nextInt();
            //since undirected graph will have same weight for both the sides.
            adjMatrix[v1][v2] = weight;
            adjMatrix[v2][v1] = weight;
            
            
        }
        
        dijkstra(adjMatrix);
        
    
    }
}