#include <fstream>
#include <iostream>
#include <climits>
#include <cstring>
#include <functional>
#include <vector>
#include <queue>

using namespace std;

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

vector<pair<long,long> > g[50005];
priority_queue <long,vector<long>,greater<long> > min_pq;
long d[50005];

int n,m,x,y,c,i,k;

void Dijkstra() {
	long node;

	for (i=1;i<=n;i++) {
		d[i]=LONG_MAX;
	}
	d[1]=0;

	min_pq.push(1);
	while (!min_pq.empty()) {
		node=min_pq.top();

		for (i=0;i<g[node].size();i++) {
			if (d[node]+g[node][i].second<d[g[node][i].first]) {
				d[g[node][i].first]=d[node]+g[k][i].second;
				min_pq.push(g[node][i].first);
			}
		}

		min_pq.pop();
	}
}

int main() {
	in>>n>>m;
	for (i=1;i<=m;i++) {
		in>>x>>y>>c;
		g[x].push_back(make_pair(y,c));
	}

	Dijkstra();

	for (i=2;i<=n;i++) {
		if (d[i]==LONG_MAX)
			out<<"0"<<" ";
		else
			out<<d[i]<<" ";
	}

	return 0;
}