#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;

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;
	nod *cur;
	for (i=1; i<=n; i++) d[i]=inf, inq[i]=0;
	d[1]=0;
	inq[1]=1;
	q.push(1);
	while (!q.empty())
	{
		nd=q.front();
		q.pop();
		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);
					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;
}