#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];

queue<int> nodes;

int distances[MAX_N] = { 0 };
bool inCoada[MAX_N] = { false };

void Dijkstra()
{
	fill_n(distances, n + 1, -1);
	
	int distance;
	int crtNode;
	nodes.push(1);

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

	inCoada[1] = true;

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

		distance = distances[crtNode];

		inCoada[crtNode] = false;

		for (vector<Vecin>::iterator it = vecini[crtNode].begin(); it != vecini[crtNode].end(); it++)
		{
			int newDist = distance + it->cost;

			if (distances[it->vecin] == -1 || distances[it->vecin] > newDist)
			{
				distances[it->vecin] = newDist;

				if (!inCoada[it->vecin])
				{
					inCoada[it->vecin] = true;
					nodes.push(it->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;
}