#include<fstream>

#define N 50001
#define M 250001

using namespace std;

long n,m,i,j,k,d[N],l,t,p=0,co,deg[N]={0},*g1[N],*g2[N],a[M],b[M],e[M],q[M],u=0,o;

int main()
{
	ifstream f ("dijkstra.in");
	ofstream g ("dijkstra.out");
	f >> n >> m;
	for( k = 1 ; k <= m ; k ++ )
	{
		f >> a[ k ] >> b[ k ] >> e[ k ];
		deg[ a[ k ] ]++;
	}
	for( i = 1 ; i <= n ; deg[i] = 0,i ++)     
	{
		d[ i ] = N;
		g1[ i ] = (long*)malloc((deg[i]+1)*sizeof(long));
		g2[ i ] = (long*)malloc((deg[i]+1)*sizeof(long));
	}
	for( k = 1 ; k <= m ; k ++)
	{
		g1[ a[ k ] ][ deg[ a[ k ] ] ] = b[ k ];
		g2[ a[ k ] ][ deg[ a[ k ] ] ] = e[ k ];
		deg[ a[ k ] ]++;
	}		
	d[ 1 ] = 0;
	q[ u++ ] = 1;
	while( p != u)
	{
		t = q[ p ++ ];
		for(j = 0; j < deg[ t ] ; j ++)
			if( d[ g1[ t ][ j ] ] > d[ t ] + g2[ t ][ j ])
			{
				d[ g1[ t ][ j ] ] = d[ t ] + g2[ t ][ j ];
				q[ u++ ] = g1[ t ][ j ];
			}
	}
	for( o = 2 ; o <= n ; o ++ )
		g << d[o] % N << " " ;
	
	return 0;
}