#include <cstdio>
#include <queue>
#define dim 50100

using namespace std;

struct nod
{
	int nr, c;
	nod *urm;
};
int n, m, d[dim], inq[dim];
nod *prim[dim];
queue<int> q;

void add(nod *&p, int nr, int c)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->c=c;
	n1->urm=p;
	p=n1;
}

void bellmanford()
{
	int nd, i;
	nod *cur;
	for (i=1; i<=n; i++) d[i]=1<<30, inq[i]=0;
	d[1]=0;
	inq[1]=1;
	q.push(1);
	while (!q.empty())
	{
		nd=q.front();
		q.pop();
		cur=prim[nd];
		inq[nd]=0;
		while (cur)
		{
			if (d[cur->nr]>d[nd]+cur->c)
			{
				d[cur->nr]=d[nd]+cur->c;
				if (!inq[cur->nr])
				{
					q.push(cur->nr);
					inq[cur->nr]=1;
				}
			}
			cur=cur->urm;
		}
	}
}

int main()
{
	int a, b, c, i;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (i=1; i<=m; i++) 
	{
		scanf("%d %d %d\n", &a, &b, &c);
		add(prim[a], b, c);
	}
	bellmanford();
	for (i=2; i<=n; i++) printf("%d ", d[i]);
	return 0;
}