#include <fstream>

#include <vector>
#include <queue>

#define MAX_N 50005

using namespace std;

struct Vecin
{
	int vecin;
	int cost;
};

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

int n, m;
vector<Vecin> vecini[MAX_N];

queue<int> nodes;

int distances[MAX_N] = { 0 };

void Dijkstra()
{
	for (int i = 1; i <= n; i++)
	{
		distances[i] = -1;
	}

	int distance;
	int crtNode;
	nodes.push(1);

	distances[1] = 0;
	distance = distances[1];
	crtNode = 1;

	while (!nodes.empty())
	{
		crtNode = nodes.front();
		nodes.pop();

		distance = distances[crtNode];

		for (int i = 0; i < vecini[crtNode].size(); i++)
		{
			int newDist = distance + vecini[crtNode][i].cost;

			if (distances[vecini[crtNode][i].vecin] == -1 || distances[vecini[crtNode][i].vecin] > newDist)
			{
				distances[vecini[crtNode][i].vecin] = newDist;
				nodes.push(vecini[crtNode][i].vecin);
			}
		}
	}
}

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

	for (int i = 0; i < m; i++)
	{
		Vecin v = Vecin();

		int nod1, nod2, cost;

		fin >> nod1 >> nod2 >> cost;

		v.vecin = nod2;
		v.cost = cost;

		vecini[nod1].push_back(v);
	}

	Dijkstra();

	for (int i = 2; i <= n; i++)
	{
		fout << ((distances[i] != -1) ? distances[i] : 0) << " ";
	}

	fin.close();
	fout.close();

	return 0;
}