#include<cstdio>
using namespace std;
#define nmax 50002
#define mmax 250002
#define inf 2000000000
struct muchie
{
	long x,y,c;
}G[mmax];
long D[nmax],M,N;
int main()
{
	long i,x,y,c,ok;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&N,&M);
	for(i=1;i<=N;i++)
	{
		scanf("%ld%ld%ld",&x,&y,&c);
		G[i].x=x;
		G[i].y=y;
		G[i].c=c;
		if(x==1)
			D[y]=c;
	}
	for(i=2;i<=N;i++)
		if(D[i]==0)
			D[i]=inf;
		do
		{
			ok=1;
			for(i=1;i<=M;i++)
				if(D[G[i].y]>D[G[i].x]+G[i].c)
				{
					D[G[i].y]>D[G[i].x]+G[i].c;
					ok=0;
				}
		}
		while(!ok);
		for(i=2;i<=N;i++)
			if(D[i]!=inf)
				printf("%ld",D[i]);
			else
				printf("0 ");
			return 0;
}