using namespace std;
#include <cstdio>
#include <vector>
#include <deque>

#define Nmax 50010

vector < pair <int, int> > V[Nmax];
deque <int> Q;
int n, m, i, x, y, z, nod, fiu, cst, viz[Nmax], bst[Nmax];

void citire(){

	FILE *f = fopen("dijkstra.in", "r");

	fscanf(f,"%d %d", &n, &m);
	for(i = 1; i <= m; i++){
		fscanf(f,"%d %d %d",&x, &y, &z);
		V[x].push_back( make_pair(y, z) );
	}
	
	fclose(f);

}

void solve(){

	for(i = 1; i <= n; i++)
		bst[i] = 1 << 30;
	
	Q.push_back(1);
	bst[1] = 0; viz[1] = 1;
	
	while( !Q.empty() ){
		nod = Q.front();
		Q.pop_front();
		viz[nod] = 0;
		
		for(i = 0; i < (int)V[nod].size(); i++){
			fiu = V[nod][i].first; cst = V[nod][i].second;
			if( bst[fiu] > bst[nod] + cst ){
				bst[fiu] = bst[nod] + cst;
				if( !viz[fiu] ){
					Q.push_back(fiu);
					viz[fiu] = 1;
				}
			}
		}
		
	}

}

void afisare(){

	FILE *g = fopen("dijkstra.out", "w");

	for(i = 2; i <= n; i++){
		if(bst[i] == (1 << 30) )
			bst[i] = 0;
		
		fprintf(g,"%d ",bst[i]);
	}
	
	fclose(g);
	
}

int main(){

	citire();
	solve();
	afisare();
	
	return 0;	
}