# include <fstream>
# include <vector>
# include <queue>

using namespace std;

const int maxn = 51000, inf = 2000000003;
int n, m;
vector <int> G [ maxn ], C [ maxn ];
int gSize [ maxn ], dist [ maxn ], from [ maxn ];

struct cmp{
	bool operator () (int a, int b){
		return dist[a]>dist[b];
	}
};

priority_queue < int, vector <int>, cmp> h;



void build_graph (){
	
	int i, x, y, c;
	ifstream f ( "dijkstra.in" );
	
	f >> n >> m;
	for ( i = 0; i < m; ++ i ){
		f >> x >> y >> c;
		G [ x ] . push_back ( y );
		C [ x ] . push_back ( c );
	}
	
	f . close ();
	
	for ( i = 1; i <= n; ++ i )
		gSize [ i ] = G [ i ] . size ();
	
}

void Dijkstra(){
	
	int i, minim, cnt = n;
	
	//init
	for ( i = 2; i <= n; ++ i ){
		dist [ i ] = inf;
		from [ i ] = -1;
	}
	dist [ 1 ] = 0;
	from [ 1 ] = 0;
	h . push ( 1 );
	
	//relax
	while ( ! h . empty() && cnt ){
		minim = h . top ();
		h . pop();
		-- cnt;
		
		for ( i = 0; i < gSize [ minim ]; ++ i )
			if ( dist [ minim ] + C [ minim ] [ i ] < dist [ G [ minim ] [ i ] ] ){
				dist [ G [ minim ] [ i ] ] = dist [ minim ] + C [ minim ] [ i ];
				from [ G [ minim ] [ i ] ] = minim;
				h . push ( G [ minim ] [ i ] );
			}
	}
	
}

void afis (){
	
	ofstream g ( "dijkstra.out" );
	int i;
	
	for ( i = 2; i <= n; ++ i )
		if ( dist [ i ] != inf )
			g << dist [ i ] << ' ';
		else g << "0 ";
	g << '\n';
	
	g . close ();
	
}

int main (){
	
	build_graph ();
	Dijkstra ();
	afis ();
	
	return 0;
	
}