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

#define Nmax 50010
#define INF 0x3f3f3f3f

vector < pair <int, int> > V[Nmax];
vector < pair <int, int> >::iterator it;
deque <int> Q;
int n, m, i, x, y, z, nod, fiu, cst, bst[Nmax];
char viz[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(){

	memset(bst, INF, (n+2) * sizeof(int));
	
	Q.push_back(1);
	bst[1] = 0; viz[1] = 1;
	
	while( !Q.empty() ){
		nod = Q.front();
		Q.pop_front();
		viz[nod] = 0;
		
		for(it = V[nod].begin() ; it != V[nod].end(); it++){
			fiu = it->first; cst = it->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] == bst[0] )
			bst[i] = 0;
		
		fprintf(g,"%d ",bst[i]);
	}
	
	fclose(g);
	
}

int main(){

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