/* 
 * File:   DijkstraStiva.cpp
 * Author: slycer
 *
 * Created on January 3, 2012, 9:50 PM
 */

#include <cstdlib>
#include <vector>
#include <iostream>
#include <fstream>
using namespace std;

class Nod{
public:
    Nod( int i, int value ){
        this->i = i; 
        this->value = value; 
    }
    
    int i,value; 
};

class PQ{
public:
    int MAX; 
    Nod **data; 
    int size; 
    int *ia; 
    PQ( int max ){
        this->MAX = max; 
        data = new Nod*[max+1]; 
        ia = new int[max+1]; 
        size = 0; 
    }
    
     void add( Nod * nod ){
        //Nod *nod = new Nod( i, value );
        size++; 
        data[size] = nod;
        ia[nod->i] = size; 
        push_up( size ); 
    }
    
     void change_value ( int i, int value ){
         data[ ia[i] ] ->value = value; 
         push_up( ia[i] ); 
     }
     
    void push_up( int index ){
        while ( index/2 != 0 && data[index/2]->value>data[index]->value ){
            swap( index, index/2 ); 
            index = index/2; 
        }
    }
    
     Nod* pop_max(){
        if ( size == 0 ){
            return NULL; 
        } 
        Nod * ret = data[1]; 
        data[1] = data[size]; 
        size--;
        push_down( 1 ); 
        return ret; 
    }
    
     void push_down( int index ){
        int left = index*2; 
        int right = left+1; 
        int op=0;
        int max = data[index]->value; 
        if ( left <= size && max>data[left]->value ){
            op=left; 
            max = data[left]->value;
        }
        
        if ( right <= size && max>data[right]->value){
            op = right; 
        }
        if ( op > 0 ){
                swap( index, op ); 
                push_down( op );
        }
    }
    
     void swap( int i, int j ){
         
        Nod* aux = data[i]; 
        data[i] = data[j]; 
        data[j] = aux; 
        ia[ data[i]->i ] = i; 
        ia[ data[j]->i ] = j; 
    }
};

class Graf{
    vector<Nod*> * data; 
    int n; 
public:
    Graf( int n ){
        this->n = n; 
        data = new vector<Nod*>[n+1];
    }
    
    void add( int a, int b, int value ){
        Nod * nod = new Nod(b,value);
        data[a].push_back( nod ); 
    }
    
    int * cost_minim(){
        int * drum = new int[n+1]; 
        bool * marcat = new bool[n+1]; 
        PQ pq(n);
        for ( int i=1; i<=n; i++){
            drum[i] = 1<<30; 
            marcat[i] = false; 
        }
        marcat[1] = true; 
        drum[1] = 0; 
        pq.add( new Nod(1,0) );
        while ( pq.size > 0 ){
            Nod * top = pq.pop_max(); 
            for ( int i=0; i<data[top->i].size(); i++ ){
                Nod * next = data[ top->i ][i];
                int cost = drum[top->i] + next->value; 
                if ( cost< drum[next->i ] ){
                    drum[ next->i ] = cost; 
                    if ( marcat[ next->i ] ){
                        pq.change_value( next->i, cost );
                    } else {
                        pq.add( new Nod(next->i, cost));
                        marcat[ next->i ] = true; 
                    }
                }
            }
        }
        return drum; 
    }
    
};

/*
 * 
 */
int main(int argc, char** argv) {
    
    ifstream input("dijkstra.in");
    ofstream output("dijkstra.out");
    int n,m; 
    input >> n >> m; 
    Graf g(n); 
    for ( int i=0; i<m; i++){
        int a,b,value; 
        input >> a >> b >> value; 
        g.add(a,b,value);
    }
    int * drum = g.cost_minim();
    for ( int i=2; i<=n; i++){
        if ( drum[i] == 1<<30 ){
            drum[i] = 0; 
        }
        output << drum[i] << " " ; 
    }
}