#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, int>> dests[50001];
set<pair<int, int>> deviz;
vector<int> dist(50001, INT_MAX);

int main()
{
	int n, m;
	fin>>n>>m;

	for (int i=1; i<=m; i++)
	{
		int a, b, c;
		fin>>a>>b>>c;
		dests[a].push_back({b, c});
	}

	deviz.insert({0, 1});
	dist[1] = 0;
	while (!deviz.empty())
	{
		int el = deviz.begin()->second;
		deviz.erase(deviz.begin());

		for (const auto &dest : dests[el])
		{
			int d = dest.first, c = dest.second;
			if (dist[d] > dist[el]+c)
			{
				if (dist[d] != INT_MAX)
					deviz.erase({dist[d], d});
				dist[d] = dist[el]+c;
				deviz.insert({dist[d], d});
			}
		}
	}

	for (int i=2; i<=n; i++)
	{
		if (dist[i] == INT_MAX)
			dist[i] = 0;
		fout<<dist[i]<<" ";
	}

	fin.close();
	fout.close();
	return 0;
}