#include<iostream>
#include<string.h>
#include<algorithm>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int d[50010];

vector<pair<int, int> > G[50010];

int N, M;

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

struct comparator
{
	bool operator () (const pair<int, int> &p1, const pair<int, int> &p2)
	{
		return p1.second > p2.second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int> >, comparator> PQ;

void Dijkstra(int S)
{
	for (int i = 1; i <= N; ++i)
		d[i] = 1 << 30;

	d[S] = 0;
	PQ.push(make_pair(S, 0));
	while (PQ.size())
	{
		pair<int, int> x = PQ.top();
		PQ.pop();

		for (int i = 0; i < G[x.first].size(); ++i)
		{
			if (x.second + G[x.first][i].second < d[G[x.first][i].first])
			{
				d[G[x.first][i].first] = x.second + G[x.first][i].second;
				PQ.push(make_pair(G[x.first][i].first, d[G[x.first][i].first]));
			}
		}
	}

}

int main()
{

	in >> N >> M;

	for (int i = 1; i <= M; ++i)
	{
		int x, y, w;
		

		in >> x >> y >> w;

		G[x].push_back(make_pair(y, w));
	}
	Dijkstra(1);
	for (int i = 2; i <= N; ++i)
		if (d[i] == (1 << 30))
			out << "0";
		else
			out << d[i] << " ";

	


	return 0;
}