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

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define INF ~(1<<31)
#define NMAX 50003
#define NIL -1
#define FALSE -1
#define DIM 4000013
#define Father(x) ((x)>>1)
#define Left(x) ((x)<<1)
#define Right(x) (((x)<<1)+1)

using namespace std;

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

vector<list<NODE> > L;
int N, M, END;
int D[NMAX], H[NMAX], IN[NMAX];

void read (char *);
void Dijkstra (int);
void init (int);

void heap_create (int);
void heap_insert (int);
int pop_heap ();
void Up (int);
void Down (int);

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

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

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

	return 0;
}

void Dijkstra (int source)
{
	list<NODE>::iterator i;

	END = 0;
	init(source);
	//heap_create (N);
	H[++END] = source;

	while (END)
	{
		int u = pop_heap ();

		for (i = L[u].begin(); i != L[u].end(); ++i)
			if (D[i->to] > D[u] + i->cost)
			{
				D[i->to] = D[u] + i->cost;

				if (IN[i->to] == FALSE)
					heap_insert (i->to);
				else
					Up (IN[i->to]);
			}
	}
}

void heap_create (int dimx)
{
	//H.resize(dimx+1);
}

void Up (int p)
{
	while (p > 1 && D[H[Father(p)]] > D[H[p]])
	{
		IN[H[p]] = Father(p);
		IN[H[Father(p)]] = p;

		H[p] ^= H[Father(p)];
		H[Father(p)] ^= H[p];
		H[p] ^= H[Father(p)];

		p = Father(p);
	}
}

void heap_insert (int value)
{
	H[++END] = value;
	IN[H[END]] = END;
	Up (END);
}

int pop_heap ()
{
	int min = H[1];
	H[1] = H[END--];
	IN[H[1]] = 1;
	Down (1);

	return min;
}

void Down (int p)
{
	int left = Left(p);
	int right = Right(p);
	int to;

	if (D[H[p]] > D[H[left]] && left <= END)
		to = left;
	else
		to = p;
	if (D[H[to]] > D[H[right]] && right <= END)
		to = right;

	if (to != p)
	{
		IN[H[p]] = to;
		IN[H[to]] = p;

		H[to] ^= H[p];
		H[p] ^= H[to];
		H[to] ^= H[p];

		Down (to);
	}
}

void read (char *file)
{
	FILE *fin = fopen (FIN, "r");
	char *buffer, *pb;

	buffer = (char*) calloc(DIM, 1);

	int i;

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

	L.resize(N+1);

	NODE a;
	int from;
	char sep[] = " \n";
	fread (buffer, sizeof(char), DIM, fin);

	pb = strtok (buffer, sep);
	from = atoi (pb);
	pb = strtok (0, sep);
	a.to = atoi (pb);
	pb = strtok (0, sep);
	a.cost = atoi (pb);

	L[from].push_back (a);

	for (i = 1; i < M ; ++i)
	{
		pb = strtok (0, sep);
		from = atoi (pb);
		pb = strtok (0, sep);
		a.to = atoi (pb);
		pb = strtok (0, sep);
		a.cost = atoi (pb);

		L[from].push_back (a);
	}
	free (buffer);
	fclose (fin);

}

void init (int source)
{
	int i;

//	D.resize (N+1);
//	IN.resize (N+1);

	for (i = 2; i <= N; ++i)
	{
		D[i] = INF;
		IN[i] = FALSE;
	}

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