#include<stdio.h>


const int maxn=50005;
const int inf=30000;

struct graf
{
	int nod,cost;
	graf *next;
};

graf *a[maxn];
int n,m;
unsigned short int d[maxn];
bool q[maxn];

void add(int where,int what,int cost)
{
	graf *q= new graf;
	q->nod=what;
	q->cost=cost;
	q->next=a[where];
	a[where]=q;
}

void read()
{
	int x,y,z;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
}

void dijkstra()
{
	for(int i=2;i<=n;i++)
		d[i]=inf;
	
	int min,pmin=0;
	for(int i=1;i<=n;i++)
	{
		min=inf;
		for(int j=1;j<=n;j++)
		  if(d[j]<min && q[j]==0)
			  min=d[j],pmin=j;
		  
		q[pmin]=1;
		graf *t=a[pmin];
		while (t)
		{
			if(d[t->nod]>d[pmin]+t->cost)
				d[t->nod]=d[pmin]+t->cost;
			t=t->next;
		}
	}
}

int main()
{
	freopen("dijkstra.out","w",stdout);
	read();
	dijkstra();
	for(int i=2;i<=n;i++)
		if(d[i]==inf) printf("0 ");
	else printf("%hd ",d[i]);
}