// infoarena: problema/dijkstra //

#include <fstream>
#include <queue>
#include <vector>

#define MAXN 51000
#define MAXM 251000
#define INF (unsigned long)1<<31
using namespace std;

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

unsigned long n,m,i,j,a,b,c,len[MAXM],fin[MAXM],dist[MAXN],next;
struct cmp
{
	inline bool operator() (unsigned long a, unsigned long b) const
	{
		return dist[fin[a]] >= dist[fin[b]];
	}
};
vector<unsigned long> g[MAXN];
vector<unsigned long>::iterator it,end;
priority_queue<unsigned long, vector<unsigned long>, cmp > q;

int main()
{
	in>>n>>m;

	for(i=1; i<=m; ++i)
	{
		in>>a>>b>>c;
		g[a].push_back(i);
		len[i]=c;
		fin[i]=b;
	}

	for(i=2; i<=n; ++i)
		dist[i] = INF;

	for(it=g[1].begin(), end=g[1].end(); it!=end; it++)
		{ dist[fin[*it]] = len[*it]; q.push(*it); }

	while(!q.empty())
	{
		next = q.top();
		q.pop();

		for(it=g[fin[next]].begin(), end=g[fin[next]].end(); it!=end; ++it)
			if(dist[fin[*it]] > dist[fin[next]]+len[*it])
				{ dist[fin[*it]] = dist[fin[next]]+len[*it]; q.push(*it); }
	}
	for(i=2; i<=n; ++i)
		out<<(dist[i]!=INF ? dist[i] : 0)<<' ';

	return 0;
}