#include <fstream>
#define inf 999999999;
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n, m, x[5002],v[5002],t[5002];

int g[5002][5002];


void init(int p)
{
	for ( int i =1 ; i<=p;i++)
		for( int j = 1; j <=n;j++)			
		g[i][j] = -1;
}
void citire()
{
		 
	in>>n>>m;
	int x,y,z;
	init(n);
	for(int i = 1; i<=m;i++)	
	{ 
		in>>x>>y>>z;
		g[x][y] = z;		
	}
}

int minim()
{
	int min = inf;
	int mn = 1;
	
	for(int i = 1;i<=n;i++)
	{
		if((v[i]==0) && (x[i] < min) && x[i] != -1) { min = x[i]; mn=i;}
	}
	
	if (mn == 1 ) return 0;
	
	return mn;
}

void complete()
{
	
}

void dijkstra()
{
	int current;
	
 	v[1]=1;
	for( int i = 1; i <= n ; i++ )
	{
		x[i] = g[1][i];
		if ( x[i]>=0 ) t[i] = 1;		
	}
	x[1] = 0;
	
	current = minim();
	while( current )
	{
		
		for ( int i = 1 ; i <= n ; i++ )			
		{
			int j = g[current][i];
			int k = x[current];
			if(j>=0 && k >= 0 && j+k < x[i]) 
			{	
				x[i] = g[current][i]+x[current];
				t[i] = current;
			}
			else if ( j>=0 && x[i] == -1 )
			{
				x[i] = g[current][i]+x[current];
				t[i] = current;
			}
		}
		v[current] = 1;	
			
		current = minim();
	}	
	
}



int main()
{
	citire();
	dijkstra();
	
	for(int i =2; i<n;i++)
		out<<x[i]<<" ";
	
	out<<x[n];
	
	in.close();
	out.close();
	return 0;
}