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

using namespace std;

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

const int NMAX = 50000, INF = INT_MAX;

struct MUCHIE
{
	int v, c;
};

vector<MUCHIE> G[NMAX + 5];
vector<int> cost;
vector<bool> vis;
MUCHIE temp;
int n, m, u, v, c;

struct cmp
{
	bool operator()(int a, int b)
	{
		return cost[a] > cost[b];
	}
};

priority_queue<int, vector<int>, cmp> pq;

int main()
{
	int i, j;
	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);
	vis.assign(n + 5, false);
	cost[1] = 0;
	vis[1] = true;
	pq.push(1);
	while (!pq.empty())
	{
		u = pq.top();
		pq.pop();
		vis[u] = false;
		for (i = 0; i < G[u].size(); ++i)
		{
			temp = G[u][i];
			if (cost[u] + temp.c < cost[temp.v])
			{
				cost[temp.v] = cost[u] + temp.c;
				if (!vis[temp.v])
				{
					pq.push(temp.v);
					vis[temp.v] = true;
				}
			}
		}
	}
	for (i = 2; i <= n; ++i)
		if (cost[i] == INF)
			fout << 0 << ' ';
		else
			fout << cost[i] << ' ';
	fin.close();
	fout.close();
	return 0;
}