#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

#define Nmax 50001
#define INF 0x3f3f3f3f

int D[Nmax], H[Nmax], poz[Nmax], N, M, L;
vector<pair<int, int> > G[Nmax];

void Heap_Down(int k) {
	int son=k;
	if(2*k<=L && D[H[2*k]]<D[H[son]])
		son=2*k;
	if(2*k+1<=L && D[H[2*k+1]]<D[H[son]])
		son=2*k+1;
	if(son!=k) {
		swap(poz[H[k]],poz[H[son]]);
		swap(H[k],H[son]);
		Heap_Down(son);
	}
}

void Heap_Up(int k) {
	while(k>1 && D[H[k]]<D[H[k/2]]) {
		swap(poz[H[k]],poz[H[k/2]]);
		swap(H[k],H[k/2]);
		k/=2;
	}
}

void insert(int val) {
	H[++L]=val;
	poz[H[L]]=L;
	Heap_Up(L);
}

void erase(int k) {
	H[k]=H[L];
	L--;
	Heap_Down(k);
}

int main() {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	int i, x, y, z, min, nod, cost;
	vector<pair<int, int> >:: iterator it;
	
	scanf("%d %d",&N,&M);
	while(M--) {
		scanf("%d %d %d",&x,&y,&z);
		G[x].push_back(make_pair(y,z));
	}
	
	for(i=1; i<=N; i++)
		poz[i]=-1, D[i]=INF;
	insert(1); D[1]=0;
	while(L) {
		min=H[1]; erase(1);
		for(it=G[min].begin(); it!=G[min].end(); ++it) {
			nod=it->first; cost=it->second;
			if(D[nod]>D[min]+cost) {
				D[nod]=D[min]+cost;
				if(poz[nod]!=-1)
					Heap_Up(poz[nod]);
				else
					insert(nod);
			}
		}
	}
	
	for(i=2; i<=N; i++)
        printf("%d ",D[i] == INF ? 0 : D[i]);
	printf("\n");
	
	return 0;
}