#include <cstdio>
#include <vector>
#define MaxN 50100
#define MaxM 250100
#define MaxC 15000
#define Dim (1<<13)
#define vec first
#define cost second

using namespace std;

int n, m, poz;
unsigned st[MaxN];
unsigned short dist[MaxN];
pair<unsigned short, unsigned short> M[MaxM];
vector<unsigned short> index[MaxC];
unsigned short a[MaxM], b[MaxM], c[MaxM];
char lin[Dim];

inline void cit(unsigned short &x){
	x=0;
	while (lin[poz]<'0' || lin[poz]>'9'){
          poz++;
	      if (poz == Dim) fread(lin, 1, Dim, stdin), poz=0;
    }
	while (lin[poz]>='0' && lin[poz]<='9'){
		x = 10*x+lin[poz++]-'0';
        if (poz == Dim) fread(lin, 1, Dim, stdin), poz=0;
	}
}

inline void scrie(unsigned short k){
     char lin[12], *s;
     s=lin+sizeof(lin)-1; s[0]=' ';
     do {
        unsigned short cat=k/10;
        s--;
        s[0]=k-cat*10+'0';
        k=cat;
     } while (k);
     fwrite(s, 1, strlen(s), stdout);
}

inline void update(int nod, unsigned short d){
	if (d < dist[nod]){
		dist[nod] = d;
		ind[d].push_back(nod);
	}
}

inline void expand(int nod, unsigned short d){
	if (d > dist[nod]) return;
	for (unsigned i=st[nod]; i<st[nod+1]; i++)
		update(M[i].vec, d+M[i].cost);
}

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i=0; i<m; i++){
		cit(a[i]); cit(b[i]); cit(c[i]);
		st[--a[i]]++; b[i]--;
	}
	for (int i=0; i<n; i++)
	    st[i+1] += st[i];
	for (int i=0; i<m; i++)
	    M[--st[a[i]]] = make_pair(b[i], c[i]);
	memset(dist, 0xff, 2*n);
	update(0, 0);
	for (int i=0; i<MaxC; i++)
		for (unsigned j=0; j<ind[i].size(); j++)
		    expand(ind[i][j], i);
	for (int i=1; i<n; i++){
	    if (dist[i]>MaxC) dist[i]=0;
	    printf("%d ", dist[i]);
	}
	return 0;
}