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

using namespace std;

#define MAX_N 50005
#define INF   (1 << 30)

struct Vecin
{
	int nod;
	int cost;
};

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

int n, m;
vector<Vecin> vecini[MAX_N];
int distante[MAX_N] = { 0 };

struct CompareFunc
{
	bool operator()(int nod1, int nod2)
	{
		return distante[nod1] > distante[nod2];
	}
};

priority_queue<int, vector<int>, CompareFunc> nodeQueue;
bool                                          inQueue[MAX_N] = { false };

void Dijkstra(int startNode)
{
	for (int i = 1; i <= n; i++)
	{
		distante[i] = INF;
	}

	int node = startNode;
	distante[node] = 0;
	nodeQueue.push(node);

	inQueue[node] = true;

	while (!nodeQueue.empty())
	{
		node = nodeQueue.top();
		nodeQueue.pop();

		inQueue[node] = false;

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

			if (newDist < distante[vecini[node][i].nod])
			{
				distante[vecini[node][i].nod] = newDist;

				if (!inQueue[vecini[node][i].nod])
				{
					nodeQueue.push(vecini[node][i].nod);
					inQueue[vecini[node][i].nod] = true;
				}
			}
		}
	}
}

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

	for (int i = 0; i < m; i++)
	{
		int nod1, nod2, cost;
		fin >> nod1 >> nod2 >> cost;

		Vecin v = Vecin();
		v.nod = nod2;
		v.cost = cost;

		vecini[nod1].push_back(v);
	}

	Dijkstra(1);

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

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

	return 0;
}