#include <vector>
#include <fstream>
#include <queue>
using namespace std;

#define INF 1000000

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

void Read();
void Dijkstra(int S);
vector <vector <pair <int, int > > > G;

int d[50001];

queue <int> Q;

int n, m;

int main()
{
	Read();
	Dijkstra(1);
	for (int i = 2; i <= n; ++i )
		fout << d[i] << ' ';
	fout << '\n';
	fout.close();
	fin.close();
	return 0;
}

void Read()
{
	fin >> n >> m;
	int x, y, c;
	G.resize(n+1);
	for (int i = 2; i <= n; ++i)
		d[i] = INF;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
}

void Dijkstra(int S)
{
	Q.push(S);
	while (!Q.empty())
	{
		int k = Q.front();
		Q.pop();
		for (int i = 0; i < G[k].size(); ++i)
		{
			if (d[G[k][i].first] > d[k] + G[k][i].second)
			{
				Q.push(G[k][i].first);
				d[G[k][i].first] = d[k] + G[k][i].second;
			}
		}
	}
}