#include <fstream>
#include <vector>
#include <queue>
#include <limits>

typedef std::pair<unsigned,unsigned> PUU;
const unsigned INF=std::numeric_limits<unsigned>::max()>>1;

int main(){
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");

	unsigned n,m; fin>>n>>m;

	std::vector< std::vector<PUU> > Adj(n);

	for(unsigned i=0;i<m;++i){
		unsigned a,b,c; fin>>a>>b>>c;
		Adj[a-1].push_back( PUU(c,b-1) );
	}

	std::vector<unsigned> dist(n,INF);
	std::priority_queue< PUU, std::vector<PUU>, std::greater<PUU> > q;
	q.push(PUU(0,0));
	dist[0]=0;

	while(!q.empty()){
		unsigned c=q.top().first;
		unsigned v=q.top().second;
		q.pop();

		if(c==dist[v]){
			for(auto it=Adj[v].begin();it!=Adj[v].end();++it){
				if(dist[ it->second ] > c + it->first){
					dist[ it->second ] = c + it->first;
					q.push(PUU(dist[it->second],it->second));
				}
			}
		}

	}

	for(unsigned i=1;i<n;++i) if(dist[i]==INF) fout<<"0 "; else fout<<dist[i]<<' ';
	fout<<'\n';
}