#include<fstream>
# define Max  6000
# define Infinit 1001

using namespace std;

int a[Max][Max],n,m,s[Max],d[Max],t[Max];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void read()
{
	int i,j,x,y;
	fin>>n>>m;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			a[i][j] = Infinit;
	for(i = 1; i <= m; i++)
	{
		fin>>x>>y>>j;
		a[x][y] = j;
	}
fin.close();
}
void dijkstra()
{
	int i,j,poz=1,min;
	s[1] = 1;
	for(i = 1; i <= n; i++)
	{
		d[i] = a[1][i];
		if(a[1][i] != Infinit)
			t[i] = 1;
	}
	for(i = 1; i <= n-1; i++)
	{
		min = Infinit;
		for(j = 1; j <= n; j++)
			if(s[j] == 0)
			if(d[j] < min)
			{
				min = d[j];
				poz = j;
			}
			s[poz] = 1;
			for(j = 1; j <= n; j++)
				if(s[j] == 0)
					if(d[j] > d[poz]+a[poz][j])
					{
						d[j] = d[poz]+a[poz][j];
						t[j] = poz;
					}
	}
}
void afis()
{
	int i;
	for(i = 2; i <= n; i++)
	if(d[i] == Infinit)
	fout<<0<<" ";
	else
  	fout<<d[i]<<" ";
	fout<<"\n";
}
int main()
{
	read();
	dijkstra();
	afis();

fout.close();

return 0;

}