//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<vector>
#include<time.h>
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f

using namespace std;

int main()
{
	int n,m,i,j,k,a,b,c,d[50001],flag=0;
	vector < pair<int,int> > v[50001];
	clock_t start,stop;
	FILE *f=fopen("bell.in","r");
	
	fscanf(f,"%i%i",&n,&m);
	for(i=0;i<m;i++)
	{
		fscanf(f,"%i%i%i",&a,&b,&c);
		v[a].pb(mp(b,c));
	}
	fclose(f);

	start=clock();
	d[1]=0;
	for(i=2;i<=n;i++)
		d[i]=inf;

	for(i=0;i<n-1;i++)
	{
		flag=0;
		for(j=1;j<=n;j++)
		{
			for(k=0;k<(int) v[j].size();k++)
			{
				if(d[j]+v[j][k].second<d[v[j][k].first])
				{
					d[v[j][k].first]=d[j]+v[j][k].second;
					flag=1;
				}
			}
		}
		if(flag==0)
			break;
	}
	stop=clock();
	printf("Au trecut %f secunde\n",(double)(stop-start)/CLOCKS_PER_SEC);

	f=fopen("bell.out","w");
	for(i=2;i<=n;i++)
	{
		if(d[i]==inf)
			d[i]=0;
		fprintf(f,"%i ",d[i]);
	}
	fprintf(f,"%s","\n");
	fclose(f);
	return 0;
}