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

using namespace std;

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

const int INF = 0x3f3f3f3f;

int n, m;
vector<pair<int, int>> graf[50005];
int dist[50005];
set<pair<int, int>> s;

void dijkstra(int nod)
{
	dist[nod] = 0;
	s.insert({ 0, nod });
	while (!s.empty())
	{
		int cn = s.begin()->second;
		s.erase(s.begin());
		for (auto i : graf[cn])
		{
			if (dist[cn] + i.second < dist[i.first])
			{
				auto p = s.find({ dist[i.first], i.first });
				if (p != s.end() && dist[i.first] != INF)
					s.erase(p);
				dist[i.first] = dist[cn] + i.second;
				s.insert({ dist[i.first], i.first });
			}
		}
	}
}

int main()
{
	fin >> n >> m;
	int x, y, z;
	for (int i = 1; i <= m; i++)
	{
		fin >> x >> y >> z;
		graf[x].push_back({ y, z });
		dist[i] = INF;
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++) 
	{
		if (dist[i] == INF) 
		{
			dist[i] = 0;
		}
		fout << dist[i] << ' ';
	}
}