#include <cstdio>
#include <vector>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define NMAX 50001
#define INF 1000000001

using namespace std;
FILE * fin=fopen(IN, "r");
FILE * fout=fopen(OUT, "w");

struct vecin
{
	int vf;
	short int c;
};

vector <vecin> G[NMAX];
int n, m, x0=1;
int cmin[NMAX], prec[NMAX];
bool z[NMAX];

void citire();
void dijkstra();
void afisare();

int main()
{
 
	citire();
	dijkstra();
	afisare();
	return 0;
}

void citire()
{
	int i, x, y, c;
	vecin aux;
	fscanf(fin,"%d %d",&n,&m);
	for(i=0; i<m; i++)
	{
		fscanf(fin,"%d %d %d",&x,&y,&c);
		aux.vf=y;
		aux.c=c;
		G[x].push_back(aux);
	}
	z[x0]=1;
	for(i=1; i<=n; ++i)
	{
		prec[i] = x0;
		cmin[i] = INF;
	}
	prec[x0]=0;
	cmin[x0]=0;
 
	for(i=0; i<G[x0].size(); ++i)
		cmin[G[x0][i].vf]=G[x0][i].c;
}

void dijkstra()
{
	int i, j, mini, vfmin=0;
	for(i=1; i<=n-1; ++i)
	{
		mini=INF;
		for(j=1; j<=n; ++j)
			if(!z[j] && cmin[j]<mini)
			{
				mini=cmin[j];
				vfmin=j;
			}
		if(mini==INF)
			break;
		z[vfmin]=1;
		for(j=0; j<G[vfmin].size(); ++j)
			if(cmin[G[vfmin][j].vf]>cmin[vfmin]+G[vfmin][j].c)
			{
				cmin[G[vfmin][j].vf]=cmin[vfmin]+G[vfmin][j].c;
				prec[G[vfmin][j].vf]=vfmin;
			}
		
	}
}

void afisare()
{
	int i;
	for(i=2; i<=n; ++i)
		if(cmin[i]==INF)
			fprintf(fout, "0 ");
		else
			fprintf(fout, "%d ", cmin[i]);
}