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

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int N = 50001, INF = 1000001;
int n, d[N], viz[N];
set<pair<int, int>>s;
vector<pair<int,int>>a[N];

void dijkstra(int nod_plecare)
{
	for (int i = 1; i <= n; i++)
	{
		d[i] = INF;
	}
	d[nod_plecare] = 0;
	s.insert({ 0, nod_plecare }); // cost si nod
	while (!s.empty())
	{
		int nod = s.begin()->second;
		s.erase(s.begin());
		if (!viz[nod])
		{
			viz[nod] = 1;
			for (auto& i : a[nod])
			{
				int cost = i.first;
				int nodvec = i.second;
				if (d[nodvec] > d[nod] + cost)
				{
					d[nodvec] = d[nod] + cost;
					s.insert({ d[nodvec],nodvec });
				}
			}
		}
	}
}

int main()
{
	int m, i, j, x, y, cost;
	cin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		cin >> x >> y >> cost;
		a[x].push_back({cost,y}); // cost si nod
	}
	dijkstra(1);
	for (i = 1; i <= n; i++)
	{
		if (d[i] == INF)
			cout << 0 << ' ';
		else
			cout << d[i] << ' ';
	}

	return 0;
}