#include <fstream>
using namespace std;

int n,m,d[50002];

const int inf = 0x3f3f3f3f;

typedef struct nod
{
	int vec,pret;
	nod *urm;
} *pNod;
pNod v[50002];

typedef struct coada
{
	int bla;
	coada *hai;
} *coa;

void add(pNod &dest, int b,int c)
{
	pNod p;
	p = new nod;
	p -> vec = b;
	p -> pret = c;
	p -> urm = dest;
	dest = p;
}

void citire()
{
	ifstream f("dijkstra.in");
	
	f>>n>>m;
	int i,a,b,c;

	for (i = 1; i <= m; i++)
	{
		f>>a>>b>>c;
		add(v[a],b,c);
	}
}
int main()
{
	citire();
	
	int x,s,i;
	pNod p;
	coa q,prim,ultim;
	q=new coada;
	ultim=prim=q;
	q->bla=1;
	
	memset(d,inf,sizeof(d)); d[1]=0;
	
	while(prim!=NULL)
	{
		x=prim->bla;
		for(p=v[x];p!=NULL;p=p->urm)
		{
			s=d[x]+p->pret;
			if(s<d[p->vec])
			{
				d[p->vec]=s;
				q=new coada;
				ultim->hai=q;
				ultim=q;ultim->bla=p->vec;
				
			}
		}
		q=prim;
		prim=prim->hai;
		q->hai=NULL;delete q;
	}
	ofstream g("dijkstra.out");
	for(i=2;i<=n;i++) 
		if(d[i]==inf) g<<0<<" ";
		else g<<d[i]<<" ";
	return 0;
}