#include <cstdio>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

#define mp make_pair
#define pb push_back
#define f first
#define s second

vector<pair<int,int> > v[50001];
vector<int> sol;
priority_queue<pair<int,int> > Q;
int n,m;

void read ()
{
	
	ifstream in ("dijkstra.in");
	
	in>>n>>m;
	
	for(int a,b,c;m;--m)
	{
		in>>a>>b>>c;
		v[a].pb(mp(b,c));
	}
	
}

void solve ()
{
	
	sol.resize(n+1,INT_MAX);
	sol[1]=0;
	for(Q.push(mp(0,1));Q.size();)
	{
		int nd=Q.top().s;
		Q.pop();
		for(vector<pair<int,int> >::iterator it=v[nd].begin();it<v[nd].end();++it)
			if(sol[nd]+it->s<sol[it->f])
			{
				sol[it->f]=sol[nd]+it->s;
				Q.push(mp(sol[it->f],it->f));
			}
	}
	
}

void out ()
{
	
	freopen ("dijkstra.out","w",stdout);
	
	for(int i=2;i<=n;++i)
		printf("%d ",sol[i]);
	
}

int main ()
{
	
	read ();
	solve ();
	out ();
	
	return 0;

}