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

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

void Dijkstra() {
	int node;

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

	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() {
	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]==INT_MAX)
			out<<"0"<<" ";
		else
			out<<d[i]<<" ";
	}

	return 0;
}