#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#include<queue>

using namespace std;

#define INF 0x3f3f3f3f

int main(){
	FILE *in = fopen("dijkstra.in", "r");
	FILE *out = fopen("dijkstra.out","w");
	
	int n, m, x, y, c, cUntil;
	priority_queue < pair<int, int>, vector < pair<int,int> >, greater < pair<int,int> > > pq;
	
	fscanf(in,"%i %i", &n, &m);
	vector< pair<int, int> > adj[n+2]; //<y,cost>
	vector< pair<int, int> > :: iterator it;
	int distMin[n+1];
	
	while(m--){
		fscanf(in,"%i %i %i", &x, &y, &c); 
		adj[x].push_back( make_pair(y,c) );
	}
	
	memset(distMin, INF, sizeof(distMin));
	pq.push( make_pair(0,1) ); distMin[1] = 0;
	
	while(!pq.empty()){
		
		x = pq.top().second; cUntil = pq.top().first;
		pq.pop();
		if( distMin[x] != cUntil ) continue;
		for(it=adj[x].begin(); it!=adj[x].end(); it++){
			y = it->first; c = it->second; 
			if( distMin[y] > distMin[x] + c ){
				distMin[y] = distMin[x] + c;
				pq.push( make_pair(distMin[y],y) );
			}
		}
	}

	
	for(int i=2;i<=n;i++)
	   fprintf(out,"%i ", ( distMin[i] == INF ? 0 : distMin[i] ) );
    
	fclose(in); fclose(out);	
	return 0;
}