#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 50005;

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

int n, m, D[MAXN];
bool inQ[MAXN];
vector < pair <int, int> > G[MAXN];
queue <int> Q;

void Bellman()
{
	for (int i = 2; i <= n; ++i)
		D[i] = INF;
	Q.push(1); inQ[1] = 1;
	while (!Q.empty())
	{
		int node = Q.front(); Q.pop(); inQ[node] = 0;
		for (vector < pair <int, int> > :: iterator it = G[node].begin(); it != G[node].end(); ++it)
		{
			int v = it -> first;
			int c = it -> second;
			if (D[v] > D[node] + c)
			{
				D[v] = D[node] + c;
				if (!inQ[v])
				{
					inQ[v] = 1;
					Q.push(v);
				}
			}
		}
	}
}

int main()
{
	fin >> n >> m;
	for (int i = 1, a, b, c; i <= m; ++i)
	{
		fin >> a >> b >> c;
		G[a].push_back( make_pair(b, c) );
	}
	Bellman();
	for (int i = 2; i <= n; ++i)
		fout << (D[i] < INF ? D[i] : 0) << " ";
	fin.close();
	fout.close();
	return 0;
}