#include<fstream>
using namespace std;
int X,Y,d,D[250005],S[250005],i,j,N,M,ok,poz,Min,k;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod{
	int x,y,dist;
	nod* adr;
}*A,*p;
void citire (){
	
	f>>N>>M;
	for(int i=1;i<=M;i++){
		f>>X>>Y>>d;
		p=new nod;
		p->x =X;
		p->y =Y;
		p->dist=d;
		p->adr=A;
		A=p;
		if (X==1)
			D[Y]=d;
		
	}
}
int main(){
		for(i=2;i<=N;i++)
		D[i]=999999999;
		
	citire();
	ok=1;
	
	while (ok)
	{p=A; ok=0;
		while (p!=NULL)
			{if (D[p->y]>p->x+p->dist)
			D[p->y]=p->x+p->dist; ok=1;
			}
		
	}
	
		for(i=2;i<=N;i++)
			if(D[i]!=999999999)
				g<<D[i]<<" ";
			else
				g<<"0"<<" ";
return 0;
}