#include <cstdio>
#include <vector>
#include <utility>
#include <list>
#define Nmax 50001
#define nod first
#define cost second

using namespace std;

vector< int > d, poz, h;
vector< list< pair< int,int > > > g(Nmax, list< pair< int,int > >() );
int N, M, x, y, z, i, nrH;

inline void swap(int x, int y) { poz[h[x]] = y; poz[h[y]] = x; int temp = h[x]; h[x] = h[y]; h[y] = temp; }
void heapUp(int loc)
{
	if (loc<=1) return;
	int tata = loc >> 1;
	if (d[h[loc]] < d[h[tata]]) { swap(tata,loc); heapUp(tata); }
}
void heapDown(int loc)
{
	int fiu;
	if ((loc << 1) <= nrH)
	{
		fiu = loc << 1;
		if (fiu + 1 <=nrH && d[h[fiu]] > d[h[fiu+1]]) ++fiu;
	}
	else return;
	if (d[h[loc]] > d[h[fiu]]){ swap(loc,fiu); heapDown(fiu); }
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d\n", &N, &M);
	for(; M; --M)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		g[x].push_back(make_pair(y,z));
	}
	d.assign(N+1,0x3f3f3f3f);
	poz.assign(N+1,0);
	h.assign(N+1, 0);
	d[1]=0;
	h[++nrH] = nrH;
	poz[1] = 1;
	while (nrH)
	{
		x = h[1];
		swap(1,nrH--);
		heapDown(1);
		for (list< pair< int,int > >::iterator it = g[x].begin(); it != g[x].end(); ++it)
			if (d[it->nod] > d[x] + it->cost)
			{
				d[it->nod] = d[x] + it->cost;
				if (poz[it->nod]) heapUp(poz[it->nod]);
				else
				{
					poz[it->nod] = ++nrH;
					h[nrH] = it->nod;
					heapUp(poz[it->nod]);
				}
			}
	}
	for (i = 2, freopen("dijkstra.out", "w", stdout); i<=N; ++i) printf("%d ", d[i] == 0x3f3f3f3f ? 0 : d[i]);
	return 0;
}