#include <fstream>
//#include <queue>
#define inf 1<<30
#define dim 50100

using namespace std;

struct nod
{
	int nr, c;
	nod *urm;
};
int n, m, d[dim], inq[dim];
nod *prim[dim];
//queue<int> q;
int q[dim];

void add(nod *&p, int nr, int c)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->c=c;
	n1->urm=p;
	p=n1;
}

void bellmanford()
{
	int nd, i, st, dr;
	nod *cur;
	for (i=1; i<=n; i++) d[i]=inf, inq[i]=0;
	d[1]=0;
	inq[1]=1;
	
	st=dr=0;
	//q.push(1);
	q[0]=1;
	//while (!q.empty())
	while (st<=dr)
	{
		//nd=q.front();
		//q.pop();
		nd=q[st-(st/dim)];
		st++;
		
		cur=prim[nd];
		inq[nd]=0;
		while (cur)
		{
			if (d[cur->nr]>d[nd]+cur->c)
			{
				d[cur->nr]=d[nd]+cur->c;
				if (!inq[cur->nr])
				{
					//q.push(cur->nr);
					++dr;
					q[dr-(dr/dim)]=cur->nr;
					
					inq[cur->nr]=1;
				}
			}
			cur=cur->urm;
		}
	}
}

int main()
{
	int a, b, c, i;
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	in>>n>>m;
	for (i=1; i<=m; i++) 
	{
		in>>a>>b>>c;
		add(prim[a], b, c);
	}
	bellmanford();
	for (i=2; i<=n; i++) 
		out<<(d[i]==inf?0:d[i])<<" ";
	out<<"\n";
	in.close();
	out.close();
	return 0;
}