#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.size())
	{
		int cn = s.begin()->second;
		int cost = s.begin()->first;
		s.erase(s.begin());
		for (auto i : graf[cn])
		{
			int ncost = dist[cn] + i.first;
			if (ncost < dist[i.second])
			{
				if (dist[i.second] != INF)
					s.erase(s.find({ dist[i.second], i.second }));
				dist[i.second] = ncost;
				s.insert({ dist[i.second], i.second });
			}
		}
	}
}

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