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

#define oo 2147483647

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod
{	int to,cost;
	nod(int y,int c) { to = y , cost = c; }
};
typedef vector<nod>:: iterator it;

int N,M;
vector<nod>a[50001];
long long d[50001];

class cmp
{	public: 
	bool operator ()(int i,int j)
	{	if(d[i] < d[j]) return 1;
		return 0;
	}
};
priority_queue<int,vector<int>,cmp>q;

int main()
{	int i,j,x,y,c;
	f>>N>>M;
	for(i = 1; i <= M; i++)
	{	f>>x>>y>>c;
		a[x].push_back(nod(y,c));
	}
	for(i = 2; i <= N; i++)
		d[i] = oo;
	d[1] = 0; q.push(1);
	while(!q.empty())
	{	x = q.top(); q.pop();
		for(it k = a[x].begin(); k != a[x].end(); k++)
			if(d[k->to] > d[x] + k->cost)
				d[k->to] = d[x] + k->cost , q.push(k->to);
	}
	for(i = 2; i <= N; i++)
		if(d[i] != oo) g<<d[i]<<" ";
		else g<<0<<" ";
	f.close();
	g.close();
	return 0;
}