#include <iostream>
#include <fstream>
#define N 4096
#define infinit 2000000000
using namespace std;
int cost[N][N]; char viz[N];
int main()
{
	fstream f("dijkstra.in",ios::in), g("dijkstra.out",ios::out);
	int m,n,i,j,x,y,c,d[N],min;
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		d[i]=infinit;
		for(j=1;j<=n;j++)
			if(i!=j) cost[i][j]=infinit;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		cost[x][y]=c;
	}
	d[1]=0;
	viz[1]=1;
	for(i=1;i<=n;i++)
		d[i]=cost[1][i];
	int vf;
	do{
		min=infinit;
		for(i=1;i<=n;i++)
			if(viz[i]==0&&d[i]<min)
			{
				min=d[i]; vf=i;
			}
		if(min<infinit)
		{
			viz[vf]=1;
			for(i=1;i<=n;i++)
				if(viz[i]==0&&d[vf]+cost[vf][i]<d[i])
				{
					d[i]=d[vf]+cost[vf][i];
				}
		}
	}while(min<infinit);
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	g.close();
	f.close();
	return 0;
}