#include<fstream>
#include<cstdlib>
#define INF 9999999
using namespace std;
ofstream out("dijkstra.out");
int a[4000][4000],n,m,uz[4000],t[4000],d[4000],minim;
void citire();
void afis(int *q,int nr);
int dijkstra(int start);
int main()
{
	citire();
	dijkstra(1);
	afis(d,n);
	return 0;
}
void citire()
{
	ifstream in("dijkstra.in");
	in>>n>>m;
	int x,y,c;
	for(;m;m--)
	{
		in>>x>>y>>c;
		a[x][y]=c;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]==0&&i!=j)
				a[i][j]=INF;
}

void afis(int *q,int nr)
{
	for(int i=2;i<=nr;i++)
		if(q[i]==INF)
			out<<0<<" ";
		else
			out<<q[i]<<" ";
		out<<'\n';
}
int dijkstra(int start)
{
	int i,j,poz;
	for( i=1;i<=n;i++)
	{
		d[i]=a[start][i];
		t[i]=start;
		uz[i]=0;
	}
	uz[start]=1;
	t[start]=0;
	for(i=1;i<n;i++)
	{
		minim=INF;
		for(j=1;j<=n;j++)
			if(uz[j]==0&&d[j]<minim)
			{
				minim=d[j];
				poz=j;
			}
	uz[poz]=1;
				for(int k=1;k<=n;k++)
						if(uz[k]==0&&d[k]>d[poz]+a[poz][k])
						{
							d[k]=d[poz]+a[poz][k];
							t[k]=poz;
						}
	}
	return 1;
}