#include <cstdio>
#include <vector>
#define Nmax 50001
using namespace std;

struct heap
{
	int v1, v2, val;	// arc v1->v2
}H[Nmax];

vector<int>edge[Nmax], cost[Nmax];
const int inf = 1<<30; short viz[Nmax], gradExt[Nmax];
int n, m, k, mincost[Nmax];

void citire()
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d%d", &n, &m);
	int i, a, b, c;
	for (i=0; i<m; ++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		edge[a].push_back(b);
		cost[a].push_back(c);
		++gradExt[a];
	}
	mincost[1] = 0;
	for (i=2; i<=n; ++i)
		mincost[i] = inf;
}

void swap(int a, int b)
{
	H[a].v1 ^= H[b].v1;
	H[b].v1 ^= H[a].v1;
	H[a].v1 ^= H[b].v1;
	
	H[a].v2 ^= H[b].v2;
	H[b].v2 ^= H[a].v2;
	H[a].v2 ^= H[b].v2;
	
	H[a].val ^= H[b].val;
	H[b].val ^= H[a].val;
	H[a].val ^= H[b].val;
}

void sift(int x)
{
	int son;
	do
	{
		son = 0;
		int leftSon = x<<1;
		if (leftSon <= k)
		{
			son = leftSon;
			if (leftSon+1 <= k && H[leftSon+1].val < H[leftSon].val)
				son = leftSon+1;
			if (H[son].val >= H[x].val)
				son = 0;
		}
		if (son)
		{
			swap(x, son);
			x = son;
		}
	}
	while (son);
}

void percolate(int x)
{
	int key1=H[x].val, key2=H[x].v1, key3=H[x].v2;
	while (x>1 && key1<H[x>>1].val)
	{
		int dad = x>>1;
		H[x].val = H[dad].val;
		H[x].v1 = H[dad].v1;
		H[x].v2 = H[dad].v2;
		x = dad;
	}
	H[x].val = key1;
	H[x].v1 = key2;
	H[x].v2 = key3;
}

void del()
{
	H[1].v1 = H[k].v1;
	H[1].v2 = H[k].v2;
	H[1].val = H[k].val;
	--k;
	sift(1);
}

void Dijkstra()
{
	int v=1, nv=0;
	while (nv < m)
	{
		vector<int>::iterator i1=edge[v].begin(), i2=cost[v].begin(), stop=edge[v].end();
		while (i1 != stop)
		{
			H[++k].v1 = v;
			H[k].v2 = *i1;
			H[k].val = *i2;
			percolate(k);
			++i1; ++i2;
		}
		
		if (mincost[H[1].v1] + H[1].val < mincost[H[1].v2])
			mincost[H[1].v2] = mincost[H[1].v1] + H[1].val;
		viz[v]=1; v=H[1].v2;
		del(); ++nv;
	}
}

void afisare()
{
	freopen("dijkstra.out", "w", stdout);
	for (int i=2; i<=n; ++i)
		printf("%d ", mincost[i]==inf ? 0 : mincost[i]);
}

int main()
{
	citire();
	Dijkstra();
	afisare();
	return 0;
}