#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

const int INF = 0x3f3f3f3f;
const int MAX_N = 50010;

int n, m, z;
pii h[MAX_N];
int c[MAX_N], f[MAX_N], p[MAX_N];
vector < pii > v[MAX_N];

inline void update(int poz)
{
	h[poz].y = c[h[poz].x];

	while (poz > 1 && h[poz].y < h[poz >> 1].y)
	{
		swap(p[h[poz].x], p[h[poz >> 1].x]);
		swap(h[poz], h[poz >> 1]);
		poz >>= 1;
	}
}

inline void insert(int nod)
{
	h[++z] = mp(nod, c[nod]);
	p[nod] = z;

	update(z);
}

inline void erase()
{
	swap(p[h[1].x], p[h[z].x]);
	swap(h[1], h[z--]);

	int poz = 1;

	while (1)
	{
		int mn = INF, pz = 0;

		if (poz * 2 <= z && h[poz * 2].y < mn)
			mn = h[poz * 2].y, pz = poz * 2;
		if (poz * 2 + 1 <= z && h[poz * 2 + 1].y < mn)
			mn = h[poz * 2 + 1].y, pz = poz * 2 + 1;

		if (mn >= h[poz].y)
			break;

		swap(p[h[poz].x], p[h[pz].x]);
		swap(h[poz], h[pz]);
		poz = pz;
	}
}

int main()
{
	int i, x, y, z;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &x, &y, &z);

		v[x].pb(mp(y, z));
	}

	memset(c, INF, sizeof(c));
	c[1] = 0;

	for (i = 1; i <= n; ++i)
		insert(i);

	for (i = 1; i <= n; ++i)
	{
		int nod = h[1].x;

		forit(it, v[nod])
			if (!f[it->x] && c[it->x] > c[nod] + it->y)
			{
				c[it->x] = c[nod] + it->y;

				update(p[it->x]);
			}

		f[nod] = 1;
		erase();
	}

	for (i = 2; i <= n; ++i)
		printf("%d ", c[i]);
}