#include <fstream>

#include <vector>
#include <queue>

#define MAX_N 50005

using namespace std;

struct Vecin
{
	int vecin;
	int cost;
};

struct NodeType
{
	int node;
	int cost;
};

bool operator<(NodeType a, NodeType b)
{
	return a.cost < b.cost;
}

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

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

priority_queue<NodeType> nodes;

int distances[MAX_N] = { 0 };

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

	NodeType crtNode;
	
	crtNode.cost = 0;
	crtNode.node = 1;

	nodes.push(crtNode);

	distances[1] = 0;

	int distance = crtNode.cost;
	
	while (!nodes.empty())
	{
		crtNode = nodes.top();
		nodes.pop();

		distances[crtNode.node] = crtNode.cost;
		distance = crtNode.cost;

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

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

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;
}