#include <fstream>
#include <vector>
#define LS (node<<1)
#define RS ((node<<1)+1)
#define  INF (1<<30)
#define IMAX (1<<16)
#define NMAX 50004

using namespace std;

FILE *in = fopen("dijkstra.in","r");
FILE *out = fopen("dijkstra.out","w");

int N,M,D[NMAX],Dist[NMAX];

vector<pair<int,int> > V[NMAX];

int AInt[IMAX];

void Refresh(int node,int start,int final)
{
	if(start == final)
		AInt[node] = start;
	else
	{
		int med = (start + final) / 2;
		Refresh(LS,start,med);
		Refresh(RS,med+1,final);
		if(D[AInt[LS]] < D[AInt[RS]])
			 AInt[node] = AInt[LS];
		else AInt[node] = AInt[RS];
	}
}

void Update(int node,int start,int final,int pos)
{
	if(start == final);
	else
	{
		int med = (start + final) / 2;
		if(pos<=med)
			 Update(LS,start,med,pos);
		else Update(RS,med+1,final,pos);
		
		if(D[AInt[LS]] < D[AInt[RS]])
			 AInt[node] = AInt[LS];
		else AInt[node] = AInt[RS];
	}
}
int main ()
{
	int i,x,y,c;
	int Empty = 1;
	fscanf(in,"%d %d",&N,&M);
	while(M--)
	{
		fscanf(in,"%d %d %d",&x,&y,&c);
		V[x].push_back(make_pair(y,c));
	//	V[y].push_back(make_pair(x,c));
	}
	for(i=2;i<=N;i++)
		D[i] = Dist[i] = INF;
	
	Refresh(1,1,N);
	
	while(Empty)
	{
		x = AInt[1];//TOP
		//POP
		if(D[x] == INF)
			Empty = 1;
		D[x] = INF;
		Update(1,1,N,x);
		for(i=0;i<V[x].size();i++)
		{
			y = V[x][i].first;
			c = V[x][i].second;
			if(Dist[y] > Dist[x]+c)
				D[y] = Dist[y] = Dist[x]+c,Update(1,1,N,y),Empty ++;
		}
		Empty--;
	}
	for(i=2;i<=N;i++)
		fprintf(out,"%d ",(Dist[i]!= INF ? Dist[i] : 0));
}