#include <fstream>
#include<queue>
using namespace std;

int n,m,d[50002];
bool inqueue[50002];

const int inf = 0x3f3f3f3f;

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

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;
	queue <int> q;
	
	memset(d,inf,sizeof(d)); d[1]=0;
	inqueue[1]=1;
	q.push(1);
	while(!q.empty())
	{
		x=q.front();
		inqueue[x]=0;
		q.pop();
		for(p=v[x];p!=NULL;p=p->urm)
		{
			s=d[x]+p->pret;
			if(s<d[p->vec])
			{
				d[p->vec]=s; 
				if(!inqueue[p->vec])
				{
					q.push(p->vec);
					inqueue[p->vec]=1;
				}
			}
		}
	}
	ofstream g("dijkstra.out");
	for(i=2;i<=n;i++) 
		if(d[i]==inf) g<<0<<" ";
		else g<<d[i]<<" ";
	return 0;
}