#include <fstream>
#include <set>
#include <vector>
#define PB push_back
#define MP make_pair
#define MAX_N 50005
#define INF 1000000000

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int n, m, d[MAX_N];
vector <int> v[MAX_N], c[MAX_N];
set < pair <int , int> > SET;

void read ()
{
	f >> n >> m;
	
	for (int i = 1; i <= m; i++)
	{
		int a, b, cost;
		f >> a >> b >> cost;
		v[a].PB(b);
		c[a].PB(cost);
	}
}

void solve ()
{
	for (int i = 2; i <= n; i++)
		d[i] = INF;
	
	SET.insert(MP(0, 1));
	
	while (SET.size() > 0)
	{
		int val = (*SET.begin()).first;
		int x = (*SET.begin()).second;
		SET.erase(*SET.begin());
		
		for (int i = 0; i < v[x].size(); i++)
			if (d[ v[x][i] ] > val + c[x][i])
			{
				d[ v[x][i] ] = val + c[x][i];
				SET.insert( MP (d[ v[x][i] ], v[x][i]));
			}
	}
	
	for (int i = 2; i <= n; i++)
		if (d[i] == INF) g << 0 << " ";
		else g << d[i] << " ";
	
	f.close();
	g.close();
}

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