#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <queue>
#include <fstream>
#include <stdio.h>
using namespace std;

#define nNodesMax 50010
#define nEdgesMax 250010
#define INF 300000

FILE* inputFile;
FILE* outputFile;


#define cin f
#define cout g
struct Nod
{
	int vf;
	int cost;
	Nod(int vf, int cost):vf{vf},cost{cost}
	{
	}
};


struct Nd
{
public:
	Nd* next;
	Nod nod;
};

struct Comp
{
	bool operator()(Nod m1, Nod m2) const
	{
		return m1.cost > m2.cost;
	}
};
int freq[nNodesMax];
int nNodes, nEdges;
int dist[nNodesMax];
vector<Nod> vecini[nNodesMax];

void Dijkstra()
{
	priority_queue<Nod, vector<Nod>, Comp> queue;

	Nod nod = Nod{ 1,0 };
	for (int i = 2; i <= nNodes;i++)
	{
		dist[i] = INF;
	}
	queue.push(nod);
	while(!queue.empty())
	{
		nod = queue.top();
		queue.pop();
		if (freq[nod.vf] == 1)
			continue;
		freq[nod.vf] = 1;
		for(auto &it : vecini[nod.vf])
		{
			if(dist[nod.vf] + it.cost < dist[it.vf])
			{
				dist[it.vf] = dist[nod.vf] + it.cost;
				queue.push(Nod{ it.vf,dist[it.vf] });
			}
		}
	}
	for (int i = 2; i <= nNodes;i++)
	{
		if(dist[i] != INF)
			fprintf(outputFile,"%d ",dist[i]);
		else fprintf(outputFile, "%d ", 0);
	}
}

int main()
{
	int currentNode, nextNode, cost;
	inputFile = fopen("dijkstra.in", "r");
	outputFile = fopen("dijkstra.out", "w");
	fscanf(inputFile, "%d %d", &nNodes, &nEdges);
	for (int i = 1; i <= nEdges;i++)
	{
		fscanf(inputFile, "%d %d %d", &currentNode, &nextNode, &cost);
		vecini[currentNode].push_back(Nod{ nextNode,cost });
	}
	Dijkstra();
	return 0;
}