#include<fstream>
#include<list>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>

#define NMAX 50005
#define MMAX 250005
#define INF 65531
#define IN "dijkstra.in"
#define IN1 "in1.txt"
#define OUT "dijkstra.out"

enum color {ALB, GRI, NEGRU};

using namespace std;
typedef struct
{
	int value;
	int cost;
} NOD,*PNOD;

int N, M;
int d[NMAX], C[NMAX], W[NMAX], F[NMAX];

vector<list<NOD> > L;
set<int> S;
vector<int> Q;

void Dijkstra (int s, int dest);
bool cmpd (int a, int b);
int cost (int i, int j);

int main (int argc, char **argv)
{

	int i;
	list<NOD>::iterator it;

	FILE *fin = fopen (IN, "r");

	fscanf(fin, "%d%d", &N, &M);
	L.resize(N+1);

	for (i = 0; i < M; ++i)
	{
		int x, y, z;
		NOD aux;
		fscanf(fin, "%d%d%d", &x, &y, &z);
		aux.value = y;
		aux.cost = z;
		L[x].push_back(aux);
	}

	fclose (fin);

	Dijkstra (1, N);

	FILE *fout = fopen (OUT, "w");

	fprintf(fout, "%d", d[2]);
	for (i = 3; i <= N; ++i)
		fprintf(fout, " %d", d[i]);
	
	fclose(fout);

	return 0;
}

bool cmpd (int i, int j)
{
	return  d[i] > d[j];
}

int cost (int s, int d)
{
	list<NOD>::iterator it;

	if (d == s)
		return 0;
	for (it = L[s].begin(); it != L[s].end(); ++it)
		if (it->value == d)
			return it->cost;
	return INF;
}

void Dijkstra (int s, int dest)
{
	int i;
	vector<int> heap;

	for (i = 1; i <= N; ++i)
	{
		heap.push_back(i);
		d[i] = INF;
	}

	list<NOD>::iterator j;

	for (j = L[s].begin(); j != L[s].end(); ++j)
		d[j->value] = j->cost;

	make_heap (heap.begin(), heap.end(), cmpd);

	while (!heap.empty())
	{
		int u = heap.front();
		S.insert (u);
		C[u] = NEGRU;
		for (j = L[u].begin(); j != L[u].end(); ++j)
		{
			if (d[(j->value)] > d[u] + cost (u, j->value))
			{
				d[j->value] = d[u] + cost (u, j->value);
				F[j->value] = u;
			}
		}
		pop_heap (heap.begin(), heap.end());
		heap.pop_back();
	}
}