#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

#define Nmax 50001
#define INF 0x3f3f3f3f

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

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

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(H[k],H[son]);
		swap(poz[H[k]],poz[H[son]]);
		Heap_Down(son);
	}
}

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

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

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

int main() {
	int i, j, c, min, nod, cost;
	
	f>>N>>M;
	while(M--) {
		f>>i>>j>>c;
		G[i].push_back(make_pair(j,c));
	}
	for(i=1; i<=N; i++) {
		D[i]=INF;
		poz[i]=-1;
	}
	D[1]=0; insert(1);
	while(L) {
		min=H[1]; erase(1);
		for(vector<pair<int, int> >:: iterator 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++)
		if(D[i]==INF)
			g<<0<<" ";
		else
			g<<D[i]<<" ";
	
	f.close();
	g.close();
	
	return 0;
}