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

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define INF 65535
#define NIL -1
#define ALB 0
#define GRI 1
#define NEGRU 2

using namespace std;

typedef struct
{
	unsigned short to;
	unsigned short cost;
}NODE;

vector<list<NODE> > L;
int N, M;
vector <unsigned int> P, D;
vector <char> POZ;
vector <unsigned short> heap;

void read (char *);
void Dijkstra (unsigned short);
void init (unsigned short);
void Relax (unsigned short, unsigned short);
unsigned short cost (unsigned short, unsigned short);

int main(int argc, char **argv)
{
	read (argv[1]);
	Dijkstra(1);

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

	for (i = 2; i <= N; ++i)
		fprintf(fout, "%d ", D[i] == INF? 0 : D[i]);
	fclose (fout);

	return 0;
}

void read (char *filename)
{
	FILE *fin = fopen (IN, "r");
	int i;

	fscanf(fin, "%d%d", &N, &M);

	L.resize(N+1);
	for (i = 0; i < M; ++i)
	{
		short from;
		short to, cost;
		NODE aux;
		fscanf (fin, "%hu%hu%hu", &from, &to, &cost);
		aux.to = to;
		aux.cost = cost;
		L[from].push_back(aux);
	}

	fclose (fin);
}

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

bool cmpa (NODE i, NODE j)
{
	return i.cost > j.cost;
}

void Dijkstra (unsigned short source)
{
	set <unsigned short> S;
	//int i;
	list<NODE>::iterator j;

	init(source);

	heap.push_back(source);
	//make_heap (heap.begin(), heap.end(), cmpd);

	/*printf("INITIAL HEAP:\n");
		for (i = 0; i < (int)heap.size(); ++i)
			printf("\t%d - cost : %d\n", heap[i], D[heap[i]]);
		printf("\n");*/

	while (!heap.empty())
	{
		//printf("===================WHILE==============\n");
		int u = heap.front();
		pop_heap (heap.begin(), heap.end(), cmpd);
		heap.pop_back();

		S.insert (u);
		for (j = L[u].begin(); j != L[u].end(); ++j)
		{
		//	printf("\t------RELAXEAZA-------\n");
			if (D[j->to] > D[u] + j->cost)
			{
				D[j->to] = D[u] + j->cost;
				P[j->to] = u;
				if (POZ[j->to] == NIL)
				{
					heap.push_back(j->to);
					push_heap (heap.begin(), heap.end(), cmpd);
					POZ[j->to] = 1;
				}
			}
		}

		/*printf("HEAP:\n");
		for (i = 0; i < (int)heap.size(); ++i)
			printf("\t%d - cost : %d\n", heap[i], D[heap[i]]);
		printf("\n");*/

		}
}

void init (unsigned short source)
{
	int i;

	P.resize (N+1);
	D.resize (N+1);
	POZ.resize (N+1);

	for (i = 1; i <= N; ++i)
	{
		P[i] = NIL;
		D[i] = INF;
		POZ[i] = NIL;
	}

	D[source] = 0;
	POZ[source] = 1;
}

void Relax (unsigned short from, unsigned short to)
{
	if (D[to] > D[from] + cost (from, to))
	{
		D[to] = D[from] + cost (from, to);
		P[to] = from;
	}
}

unsigned short cost (unsigned short from, unsigned short to)
{
	list<NODE>::iterator i;
	if (from == to)
		return 0;

	for (i = L[from].begin(); i != L[from].end(); ++i)
		if (i->to == to)
			return i->cost;
	return INF;
}