#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;
queue<long> q;
long d[50001];

long n,m,i;

void Dijkstra() {
	long node;

	q.push(1);
	while (!q.empty()) {
		node=q.front();
		q.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;
				q.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;
}