#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[50001];
priority_queue <long,vector<long>,greater<long> > min_pq;
long d[50001];

long n,m,i;

void Dijkstra() {
	long node;

	min_pq.push(1);
	while (!min_pq.empty()) {
		node=min_pq.top();
		min_pq.pop();
		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[node][i].second;
				min_pq.push(g[node][i].first);
			}
		}
	}
}

int main() {
	long x,y,c;

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

	for (i=2;i<=n;i++) {
		d[i]=1<<30;
	}

	Dijkstra();

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

	return 0;
}