#include<fstream>
#include<set>
#include<cstring>
#include<vector>
#define INF 1000000

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int n, m, dist[50005];
vector < pair < int, int > > nod[50005];

int main(){
		cin>>n>>m;
		
		for(int i=1; i<=m; ++i){
			int a, b, c;
			cin>>a>>b>>c;
			nod[a].push_back(make_pair(b,c));
		}
	for(int i=2; i<=n; ++i) dist[i]=INF;
	set < pair < int, int > > noistim;
	
	noistim.insert(make_pair(0,1));
	
	while(!noistim.empty()){
		int cn = noistim.begin()->second;
		int cd = noistim.begin()->first;
		noistim.erase(noistim.begin());
		
		for(vector < pair < int, int > >::iterator it = nod[cn].begin(); it!=nod[cn].end(); ++it){
			int to = it->first;
			int cost = it->second;
			if(dist[to]>dist[cn]+cost){
				if(dist[to] != INF){
					noistim.erase(noistim.find(make_pair(dist[to], to)));
				}
				dist[to] = dist[cn]+cost;
				noistim.insert(make_pair(dist[to], to));
			}
		}	
	}
	
	for(int i=2; i<=n; ++i){
		if(dist[i]==INF) dist[i]=0;
		cout<<dist[i]<<" ";
	}
	
	
	
	return 0;
}