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

using namespace std;

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

const int inf = 999999999;
int n, m;
vector<vector<int>> c;
queue<int> s;
vector<int> d, o;

void wdf(int k)
{
	o[k] = 1;
	for (int i = 1; i <= n; i++)
	{
		if (i != k && c[k][i] > - 1)
		{
			if (c[k][i] + d[k] < d[i])
			{
				d[i] = c[k][i] + d[k];
				s.push(i);
			}
		}
	}
	s.pop();
	if (!s.empty())
	{
		
			while (o[s.front()] == 1)
				s.pop();
			wdf(s.front());
	}
}

int main()
{
	fi >> n >> m;
	vector<vector<int>> a1(n + 1, vector<int>(n + 1, -1));
	c = a1;
	vector<int> d1(n + 1, inf);
	d = d1;
	o = d1;
	d[1] = 0;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c1;
		fi >> x >> y >> c1;
		c[x][y] = c1;
	}
	s.push(1);
	wdf(s.front());
	for (int i = 2; i <= n; i++)
	{
		if (d[i] == inf)
			d[i] = 0;
		fo << d[i] << " ";
	}
}