#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

#define INF 0x3f3f3f3f

ifstream is("dijkstra.in");
ofstream os("dijkstra.out");

struct Edge{
	int y, cost;
	
	bool operator < (const Edge& c ) const
	{
		return c.cost < cost;
	}
};

vector<vector<Edge> > G;
vector<int> D;
priority_queue<Edge> Q;
bitset<50001> v;
int n, m;

void Read();
void Dijkstra(int node);

int main()
{
	Read();
	Dijkstra(1);
	for ( vector<int>::iterator it = D.begin() + 2; it != D.end(); ++it )
		if ( *it == INF )
			os << 0 << ' ';
		else
			os << *it << ' ';
	
	is.close();
	os.close();
	return 0;
}

void Read()
{
	is >> n >> m;
	G = vector<vector<Edge> >(n + 1);
	D = vector<int>(n + 1, INF);
	
	int x, y, cost;
	for ( int i = 1; i <= m; ++i )
	{
		is >> x >> y >> cost;
		G[x].push_back({y, cost});
	}
}

void Dijkstra(int node)
{
	int x, cost;
	D[node] = 0;
	Q.push({node, 0});
	while ( !Q.empty() )
	{
		x = Q.top().y;
		cost = Q.top().cost;
		Q.pop();
		if ( v[x] ) continue;
		v[x] = 1;
		for ( const auto& g : G[x] )
		{
			if ( D[g.y] > cost + g.cost )
			{
				D[g.y] = cost + g.cost;
				Q.push({g.y, D[g.y]});
			}
		}
		
		while ( !Q.empty() && v[Q.top().y] )
			Q.pop();
		
	}
}