#include <cstdio>
#include <vector>
#define NMAX 55001
#define INF 1000000000
using namespace std;
void citire();
void initializare();
void rezolvare();
void scrie();
int N,M;
vector<int> G[NMAX],H[NMAX];
int VAL[NMAX];
int PRE[NMAX];
bool F[NMAX];

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	initializare();
	citire();
	rezolvare();
	scrie();
	
	return 0;
}

void initializare()
{
	for(int i=1;i<=NMAX;i++)
	{
		if(!VAL[i])
			VAL[i]=INF;
		PRE[i]=1;
	}
	PRE[1]=0;
	VAL[1]=0;
	F[1]=1;
}

void citire()
{
	int x,y,z;
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		G[x].push_back(y);
		H[x].push_back(z);
		if(x==1)
			VAL[y]=z;
	}
		
}

void rezolvare()
{
	int dmin;
	int vfmin;
	vector<int>::iterator it,ih;
	
	for(int i=1;i<N;i++)
	{
		dmin=INF;
		for(int j=1;j<=N;j++)
			if(!F[i] && VAL[i]<dmin)
			{
				dmin=VAL[i];
				vfmin=i;
			}
		F[vfmin]=1;
		for( it=G[vfmin].begin() , ih=H[vfmin].begin() ; it!=G[vfmin].end() ;it++,ih++)
			if(VAL[vfmin]+*ih<VAL[*it])
			{
				VAL[*it]=VAL[vfmin]+*ih;
				PRE[*it]=vfmin;
			}
	}
		
}

void scrie()
{

		
	for(int i=2;i<=N;i++)
	{
		if(VAL[i]==INF)
			printf("%d ",0);
		else
			printf("%d ",VAL[i]);
	}
}