#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#define dim 100006
#define inf 20000000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
queue<int>s;
vector< pair <int ,int > > G[dim];
int n,m,D[dim],i,x,a,b,c;

int main () {
	
	f>>n>>m;
	
	for(i=1;i<=m;++i){
		f>>a>>b>>c;
		G[a].push_back(make_pair(b,c));
	}
	for(i=1;i<=n;++i)
		D[i]=inf;
	D[1]=0;
	
	s.push(1);
	for(	;!s.empty() ;	 ) {
		
		x=s.front();
		s.pop();
		
		for(int i=0;i<G[x].size();++i) {
			
			if(D[G[x][i].first]>D[x]+G[x][i].second){
				D[G[x][i].first]=D[x]+G[x][i].second;
				s.push(G[x][i].first);
			}
			
		}
		
	}		
	
	for(i=2;i<=n;++i){
		if(D[i]==inf)
			g<<"0 ";
		else
			g<<D[i]<<" ";
	}
	return 0;
}