#include <queue>
#include <vector>
#define NMAX 50005
#define DMAX 0x3f3f3f3f

using namespace std;
typedef pair<int,int> pereche;

void citire(),rezolvare(),afisare();
int M,N;
vector<pereche> G[NMAX];
int distanta[NMAX];

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

void afisare()
{
	for(int i=2;i<=N;i++)
		printf("%d ",distanta[i]!=DMAX?distanta[i]:0);
}

void rezolvare()
{
	queue<int> coada;
	bool inCoada[NMAX];
	memset(distanta,DMAX,sizeof(distanta));
	memset(inCoada,false,sizeof(inCoada));
	
	coada.push(1);
	inCoada[1]=true;
	distanta[1]=0;
	
	while(!coada.empty())
	{
		int tata=coada.front();
		coada.pop();
		for(vector<pereche>::iterator i=G[tata].begin();i!=G[tata].end();i++)
			if(distanta[(*i).first]>distanta[tata]+(*i).second)
			{
				distanta[(*i).first]=distanta[tata]+(*i).second;
				if(!inCoada[(*i).first])
					coada.push((*i).first),
					inCoada[(*i).first]=true;
			}
		inCoada[tata]=false;
	}
}

void citire()
{
	int s,d,c;
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++)
		scanf("%d %d %d",&s,&d,&c),
		G[s].push_back(pereche(d,c));
}