#include <stdio.h>

#include <vector>
#include <queue>

#define MAX_N 50005

using namespace std;

struct Vecin
{
	int vecin;
	int cost;
};

FILE* fin;
FILE* fout;

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

priority_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.top();
		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 = fopen("dijkstra.in", "r");
	fout = fopen("dijkstra.out", "w");

	fscanf(fin, "%d %d", &n, &m);
	
	for (int i = 0; i < m; i++)
	{
		Vecin v = Vecin();

		int nod1, nod2, cost;

		fscanf(fin, "%d %d %d", &nod1, &nod2, &cost);
		
		v.vecin = nod2;
		v.cost = cost;

		vecini[nod1].push_back(v);

		// aparent e graf orientat
	}

	Dijkstra();

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

	fclose(fin);
	fclose(fout);

	return 0;
}