#include <fstream>
#include <vector>
using namespace std;

ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");

const int OO = 1<<29, dim = 100005;
struct vec { int v, c; };
vector <vec> V[dim];
int N, M, H[dim], D[dim], viz[dim], P[dim];

void cit ()
{
	vec x;
	fi >> N >> M;
	for (int i = 1, a; i <= M; i++)
	{
		fi >> a >> x.v >> x.c;
		V[a].push_back (x);
	}	
}

void upheap (int f)
{
	int t = f >> 1;
	while (t != 0 && D[H[t]] > D[H[f]])
	{
		swap (H[f], H[t]);
		swap (P[H[f]], P[H[t]]);
		
		f = t;
		t = f >> 1;
	}	
}

void downheap (int t)
{
	int f = t << 1;
	if (f+1 <= H[0] && D[H[f+1]] < D[H[f]])
		f++;
	while (f <= H[0] && D[H[f]] < D[H[t]])
	{
		swap (H[t], H[f]);
		swap (P[H[t]], P[H[f]]);
		
		t = f;
		f = t << 1;
		if (f+1 <= H[0] && D[H[f+1]] < D[H[f]])
			f++;
	}	
}

void dijkstra ()
{
	for (int i = 1; i <= N; i++)
		D[i] = OO;
	D[1] = 0;
	H[++H[0]] = 1;
	P[1] = 1;
	
	for (int i = 2, n, v, c; i <= N; i++)
	{
		n = H[1];
		viz[n] = 1;
		H[1] = H[H[0]];
		P[H[H[0]]] = 1;
		H[0]--;		
		downheap (1);
		
		for (int j = 0; j < V[n].size(); j++)
		{
			v = V[n][j].v;
			c = V[n][j].c;
			if (viz[v] == 0 && D[v] > D[n] + c)
			{
				D[v] = D[n] + c;
				if (P[v] == 0)
				{
					P[v] = ++H[0];
					H[H[0]] = v;
				}
				upheap (P[v]);
				downheap (P[v]);
			}
		}		
	}	
}

void afi ()
{
	for (int i = 2; i <= N; i++)
	{
		if (D[i] == OO)
			D[i] = 0;
		fo << D[i] << ' ';
	}	
	fo << '\n';
}

int main ()
{
	cit ();
	dijkstra ();
	afi ();
	return 0;
}