#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int INF = 2000000000;

struct VERTEX
{
	int v, c;
};

queue<int> q;
vector<VERTEX> G[50005];
vector<int> cost;
VERTEX temp;
int n, m, u, v, c, nou, i;

int main()
{
	fin >> n >> m;
	for (i = 0; i < m; ++i)
	{
		fin >> u >> v >> c;
		temp.v = v;
		temp.c = c;
		G[u].push_back(temp);
	}
	cost.assign(n + 5, INF);
	cost[1] = 0;
	q.push(1);
	while (!q.empty())
	{
		nou = q.front();
		q.pop();
		for (i = 0; i < G[nou].size(); ++i)
		{
			if (cost[nou] + G[nou][i].c < cost[G[nou][i].v])
			{
				cost[G[nou][i].v] = cost[nou] + G[nou][i].c;
				q.push(G[nou][i].v);
			}
		}
	}
	for (i = 2; i <= n; ++i)
		if (cost[i] == INF)
			fout << 0 << ' ';
		else
			fout << cost[i] << ' ';
	fin.close();
	fout.close();
	return 0;
}