#include<iostream>
#include<fstream>
using namespace std;
int viz[50001],d[50001],a[10001][10001],n,m;


int rec(int x)
{
	int i;
	viz[x]=1;
	for(i=1;i<=n;i++)
		if(a[x][i] && viz[i]==0)
		{
			if(d[x]+a[x][i]<d[i]) d[i]=d[x]+a[x][i];
			rec(i);
		}
	viz[x]=0;

}
int main()
{
	int i,aa,bb,cc;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>aa>>bb>>cc;
		a[aa][bb]=cc;
	}
	for(i=2;i<=n;i++)
		if(a[1][i])
			d[i]=a[1][i];
		else d[i]=32000;
	viz[1]=1;	
	for(i=2;i<=n;i++)
		if(a[1][i])
		{
			viz[i]=1;
			rec(i);
			viz[i]=0;
		}
			
		
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
}