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

using namespace std;
typedef unsigned int uint;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

class Graph
{
	struct cost
	{
		uint node,weight;
	};

	uint V;
	vector<vector<cost>> adj;

public:
	Graph(const uint V);
	void Add_edge(uint &src, uint &dest, uint &weight);
	void Dijkstra(const uint start);
};

Graph::Graph(const uint V)
{
	this->V = V;
	adj.assign(V + 1, vector<cost>());
}

void Graph::Add_edge(uint &src, uint &dest, uint &weight)
{
	adj[src].push_back({dest,weight});
}

void Graph::Dijkstra(const uint start)
{
	auto cmp = [](cost a, cost b)
	{
		return a.weight > b.weight;
	};
	priority_queue<cost, vector<cost>, bool (*)(cost,cost)> Q(cmp);

	const uint oo = ~0;
	vector<uint> dist(V + 1, oo);

	dist[start] = 0;
	Q.push({start,0});

	while (!Q.empty())
	{
		cost n = Q.top();
		Q.pop();

		for (auto &i : adj[n.node])
		{
			if (dist[i.node] == oo)
			{
				dist[i.node] = dist[n.node] + i.weight;
				Q.push(i);
			}
		}
	}

	for (uint i = 1; i <= V; ++i)
		if (i != start)
			fout << dist[i] << ' ';
}

int main()
{
	uint n,m;
	fin >> n >> m;

	Graph G(n);

	for (uint x,y,c, i = 0; i < m; ++i)
	{
		fin >> x >> y >> c;
		G.Add_edge(x,y,c);
	}

	G.Dijkstra(1);
}