#include<cstdio>
#define INF 1000000000
using namespace std;

#define NMax 50001

struct NodGR
{
	int inf,cost;
	struct NodGR* next;
};

typedef NodGR* NGR;

NGR a[NMax];
int n,m;

void read();
void adaug(int x,int y,int c);
void bell(int x);

int  main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	read();
	bell(1);
	return 0;
}

void read()
{
	int i,x,y,c;
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		adaug (x,y,c);
	}
}

void adaug(int x,int y,int c)
{
	NGR p=new NodGR;
	p->inf=y;
	p->cost=c;
	p->next=a[x];
	a[x]=p;
}

void bell(int x)
{
	int Q[30*NMax],d[NMax];
	int i,pr,ul,z,gg;
	NGR q;
	for (i=1;i<=n;++i)
		d[i]=INF;
	d[x]=0;
	pr=ul=1;
	Q[pr]=x;
	while (pr<=ul)
	{
		z=Q[pr];
		for (q=a[z];q;q=q->next)
		if (q->inf!=x)
		{
			gg=q->inf;
			if (d[gg]>d[z]+q->cost)
			{
				d[gg]=d[z]+q->cost;
				Q[++ul]=gg;
			}
		}
		++pr;
	}
	d[i]=0;
	for (i=2;i<=n;++i)
		printf("%d ",d[i]);
}