#include<fstream>


using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n,m;
typedef struct nod
{
	int x;	
	int cost;
	nod *a;
} *pNod;

pNod g[50002];

int v[50002];
int x[50002] = { -1 };
void add(pNod &dest,int val,int cost)
{
	pNod p;
	p = new nod;
	p -> x = val;
	p -> cost = cost;
	p -> a = dest;	
	
	dest = p;
	
}

void citire()
{
	int x,y,z;
	
	in>>n>>m;
	

	
	for( int i = 1 ; i <= m ; i++ )
	{
		in>>x>>y>>z;		
		add(g[x],y,z);
	}
}

void travel(int nod, int cost)
{
	pNod p;
	
	for( p = g[nod] ; p != NULL ; p = p -> a ) 
	{
		int a = p->x;
		int b = p->cost;
		
		if(x[a] == -1 )
			x[a] = cost + b;
		else if ( cost + b < x[a] ) x[a] = cost + b;
	}
}

int minim()
{
	int m = 999999999;
	int no = -1;
	for ( int i = 1 ; i<=n ; i++ )
	{
		if( m > x[i] && x[i] != -1 && v[i] == 0) { m = x[i]; no = i; }
	}
	if ( no == -1) return 0;
	return no;
}

void dijkstra()
{
	travel ( 1 , 0 );
	v[1] = 1;
	int current = minim();
	
	while(current)
	{
		
		travel ( current, x[current] ) ;
		
		v[current] = 1;
		current = minim();
	}
}

void afis()
{
	for ( int i =2 ; i<n;i++)
		if( x[i] == -1 ) out<<"0 ";
	else out<<x[i]<<" ";
		
		if( x[n] == -1 ) out<<"0";
	else out<<x[n];
}

void init()
{
	for ( int i =1 ; i<=n;i++)
		x[i] = -1;	
}
int main()
{	
	citire();
	init();
	
	dijkstra();
	afis();
	
	return 0;
}