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

struct nod
{
	int val, cost;
};
vector <nod> grf[50001];
class comp
{
public:
	bool operator()(nod a, nod b)
	{
		return a.cost<b.cost;
	}
};
priority_queue <nod, vector<nod>, comp> coada;
int d[50001];
int main()
{
	int n, m, i, a, b, c;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1; i<=m; i++)
	{
		f>>a>>b>>c;
		nod act;
		act.val=b;
		act.cost=c;
		grf[a].push_back(act);
	}
	for(i=1; i<=n; i++)
	{
		d[i]=10000000;
	}
	nod act;
	act.val=1;
	act.cost=0;
	coada.push(act);
	d[1]=0;
	while(!coada.empty())
	{
		int cx=coada.top().val;
		if(d[cx]!=coada.top().cost)
		{
			coada.pop();
			continue;
		}
		coada.pop();
		for(i=0; i<grf[cx].size(); i++)
		{
			if(d[cx]+grf[cx][i].cost<d[grf[cx][i].val])
			{
				coada.push(grf[cx][i]);
				d[grf[cx][i].val]=d[cx]+grf[cx][i].cost;
			}
		}
	}
	for(i=2; i<=n; i++)
	{
		if(d[i]!=10000000)
			g<<d[i]<<" ";
		else
			g<<0<<" ";
	}
}