#include <fstream>
#include <iostream>
#define right_son(x) x*2+1
#define left_son(x) x*2
#define father(x) x/2

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int maxn = 50001;
const int inf = 1 << 30;
 
struct graf
{
    int nod, cost;
    graf *next;
};

int n, m, M,H[1<<16];
graf *a[maxn];
int d[maxn],poz[maxn];
 
void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}
 
void read()
{
    fin >> n >> m;
 
    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        fin >> x >> y >> z;
        add(x, y, z);
    }
}

void sift(int K){
	int son = 1;
	while(son){
		son = 0;
		if(left_son(K) <=M){
			if(right_son(K) <= M && d[H[right_son(K)]] < d[H[left_son(K)]])
			son = right_son(K); else son = left_son(K);
			
			if(d[H[son]] < d[H[K]]){
				swap(poz[H[son]],poz[H[K]]);
				swap(H[son],H[K]);
				K = son;
			}else son = 0;
		}
	}
}

void perlocate(int K){

	for(;d[H[K]] < d[H[father(K)]] && K > 1;K/=2){
		swap(poz[H[K]],poz[H[K/2]]);
		swap(H[K],H[K/2]);
	}
}
void update_heap(int i){
				 
		if(i == 1) sift(1); else
		if(d[H[i]] < d[H[i/2]]) 
			sift(i);
		else{
			perlocate(i);
		}
}
void insert(int ind){
	
	H[++M] = ind;
	poz[ind] = M;
	perlocate(M);
}
void dijkstra(){
	
    for ( int i = 2; i <= n; ++i )
        d[i] = inf;
    H[1] = 1; 
    poz[1] = 1;
    M = 1;
    int pmin = 0;
    for ( int i = 1; i <= n; ++i )
    {	
     			pmin = H[1];
     			poz[H[1]] = -1;
     			H[1] = H[M];
     			poz[H[1]] = 1;
     			M--;
                sift(1);
                
				 
        graf *t = a[pmin];
 
        while ( t )
        {
            if ( d[ t->nod ] > d[pmin] + t->cost )
            	d[ t->nod ] = d[pmin] + t->cost;
				if(poz[t->nod] == 0){
            		insert(t->nod);
				}else if(poz[t->nod] != -1) update_heap(poz[t->nod]);
            t = t->next;
        }
        
        
    }
}

int main()
{
    read();
    dijkstra();
 
    for ( int i = 2; i <= n; ++i )
    	if(d[i] == inf) fout << 0 << ' '; else fout << d[i]<<' ';
    fout << '\n';
 
    return 0;
}