#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const unsigned INF = std::numeric_limits<unsigned>::max()>>1;

typedef pair<unsigned,unsigned> PUU;


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

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

	vector< 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(b-1,c));
	}

	vector<unsigned> dist(n,INF);

	priority_queue<PUU, vector<PUU>, greater<PUU> > q;
	q.push(PUU(0,0)); dist[0]=0;

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

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


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