#include <fstream>
#include <vector>
#define LS (node<<1)
#define RS ((node<<1)+1)
#define  INF (1<<30)
#define IMAX (1<<16)
#define NMAX 50004
#define LIM (1<<10)
#define cont ++poz == LIM ? in.read(T,LIM),poz = 0 : 0

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

/**************************/
char T[LIM+4];
int poz;
void Citeste(int &n)
{
	if(T[0] == '\0')in.read(T,LIM);
	else for(;T[poz]<'0'||T[poz]>'9';cont);
	for(n = 0;T[poz]>='0'&&T[poz]<='9';n = n*10+T[poz]-'0',cont);
}
/*************************/

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;
	Citeste(N),Citeste(M);
	while(M--)
	{
		Citeste(x),Citeste(y),Citeste(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++)
		out<<(Dist[i]!= INF ? Dist[i] : 0)<<' ';
}