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

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

string show(vector<int> x)
{
	stringstream r;
	r<<"[ ";
	for(vector<int>::iterator it=x.begin(); it!=x.end(); it++)
		r<<(*it)<<' ';
	r<<']';
	return r.str();
}


int n,m,i,j,a,b,c,len[50010],fin[50010],dist[50010],next;
struct cmp
{
	bool operator() (int a, int b)
	{
		return dist[a] > dist[b];
	}
};
vector<int> g[50010];
vector<int>::iterator it;
priority_queue<int, vector<int>, cmp > q;
bool viz[50010];

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;
	}		
	viz[1]=true;
	for(i=1; i<=n; i++)
		dist[i] = 1<<30;
	for(it=g[1].begin(); it!=g[1].end(); it++)
		dist[fin[*it]] = len[*it], q.push(fin[*it]);
		
	for(i=1; i<=n; i++)
	{
		do
			{next = q.top(); q.pop();}
		while(!q.empty() && viz[next]);
		if(q.empty())
			break;
		
		viz[next]=true;
		
		for(it=g[next].begin(); it!=g[next].end(); it++)
			if(!viz[*it] && dist[fin[*it]] > dist[next]+len[*it])
				dist[fin[*it]] = dist[next]+len[*it], q.push(fin[*it]);
	}
	for(i=2; i<=n; i++)
		out<<dist[i]<<' ';
	
	return 0;
}