#include<fstream.h>
#define NrMax 500
#define INF 100000

long d[NrMax],tata[NrMax],n,m;
int viz[NrMax],C[NrMax][NrMax];

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


void citire()
{
	long i,x,y;
	int cost;
	
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>cost;
		C[x][y]=cost;
		viz[i]=0;
	}
}

void dijkstra(long x0)
{
	long i,min,k;
	int ok;
	
	for(i=1;i<=n;i++)
	{
		viz[i]=0;
		d[i]=C[x0][i];
		tata[i]=x0;
	}
	
	tata[x0]=0;
	viz[x0]=1;
	ok=1;
	while(ok==1)
	{
		min=INF;
		
		for(i=1;i<=n;i++)
		{
			if(viz[i]==0 && d[i]<min)
			{
				min=d[i];
				k=i;
			}
		}
		
		if(min!=INF)
		{
			viz[k]=1;
			for(i=1;i<=n;i++)
			{
				if(viz[i]==0 && d[i]>d[k]+C[k][i])
				{
					d[i]=d[k]+C[k][i];
					tata[i]=k;
				}
			}
		}
		else
			ok=0;
		
	}
}

void initial()
{
	long i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
				C[i][j]=INF;
}

void afisare()
{
	long i;
	for(i=2;i<=n;i++)
		if(d[i]==INF)
			fout<<"0 ";
		else
			fout<<d[i]<<" ";
	fout<<'\n';
}

int main()
{
	fin>>n>>m;
	initial();
	citire();	
	dijkstra(1);
	afisare();
	
	fout.close();
	return 0;
}