#include<fstream>
#define dmax 31000
#define mult 10000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,cp[dmax];
short int mat[dmax][dmax];
bool t[dmax];
void dijkstra()
{	int i,r,bun,min=-1;
	r=n-1;
	while(r)
	{	min=-1;
		for(i=1;i<=n;i++)
			if(!t[i])
			{	if(cp[i]<min || min==-1)
				{	min=cp[i];
					bun=i;
				}	
			}
		t[bun]=1;
		for(i=2;i<=n;i++)	
			if(!t[i] && mat[bun][i])
				if(cp[i]>cp[bun]+mat[bun][i] && !t[i])
					cp[i]=cp[bun]+mat[bun][i];
		r--;	
	}		
}
int main()
{	int i,a,b,c;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b>>c;
		mat[a][b]=c;
	}
	in.close();
	for(i=2;i<=n;i++)
	{	if(mat[1][i])
			cp[i]=mat[1][i];
		else cp[i]=mult;
	}
	t[1]=1;
	dijkstra();
	for(i=2;i<=n;i++)
	{	if(cp[i]==mult)
			cp[i]=0;
		out<<cp[i]<<" ";
	}	
	out.close();
	return 0;
}