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

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define INF ~(1<<31)
#define NIL -1
#define ALB 0
#define GRI 1
#define NEGRU 2
#define FALSE -1
#define Father(x) ((x)>>1)
#define Left(x) ((x)<<1)
#define Right(x) (((x)<<1)+1)

using namespace std;

typedef struct
{
	int to;
	int cost;
}NODE;

vector<list<NODE> > L;
int N, M, END;
vector <int> P, D, H;
vector <int> IN;


void read (char *);
void Dijkstra (int);
void init (int);
void Relax (int, int);
int cost (int, 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);
/*
	int k;
	scanf ("%d", &k);

	for (i = k; i > 0  ; i = P[i])
		printf("%d\n", i);
		*/

	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;
				P[i->to] = u;

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

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

void Up (int p)
{
//	while (p > 1 && D[H[Father(p)]] > D[value])
	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 (file, "r");
	int i;

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

	L.resize(N+1);
	for (i = 0; i < M; ++i)
	{
		int from, to, cost;
		NODE aux;
		fscanf (fin, "%d%d%d", &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];
}

void init (int source)
{
	int i;

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

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

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

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

int cost (int from, int 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;
}