#include <fstream>
#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;
};

struct vec2{
	int v,ind;
};

vec2 H[1<<16];
int n, m, M;
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 && H[right_son(K)].v < H[left_son(K)].v)
			son = right_son(K); else son = left_son(K);
			
			if(H[son].v < H[K].v){
				swap(poz[H[son].ind],poz[H[son].ind]);
				swap(H[son],H[K]);
				K = son;
			}else son = 0;
		}
	}
}

void perlocate(int K){
	int val = H[K].v;
	for(;val < H[father(K)].v && K > 1;K/=2){
		swap(poz[H[K].ind],poz[H[K/2].ind]);
		swap(H[K],H[K/2]);
	}
}
void update_heap(int i,int val){
		if(val > H[i].v) {
			H[i].v = val;
			sift(i);
		}else{
			H[i].v = val;
			perlocate(i);
		}
}
void insert(int val,int ind){
	
	H[++M].v = val;
	H[M].ind = ind;
	poz[ind] = M;
	perlocate(M);
}
void dijkstra(){
	
    for ( int i = 2; i <= n; ++i )
        d[i] = inf;
    H[1].v = 0; 
    H[1].ind = 1;
    poz[1] = 1;
    M = 1;
    int min, pmin = 0;
    for ( int i = 1; i <= n; ++i )
    {
        min = inf;
        
                min = H[1].v, pmin = H[1].ind;
                update_heap(1, inf);
				poz[H[1].ind] = -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(d[t->nod],t->nod);
				}else if(poz[t->nod] != -1) update_heap(poz[t->nod],d[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;
}