#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);

	vector<uint> dist(V + 1, 0);

	Q.push({start,1});
	while (!Q.empty())
	{
		cost a = Q.top();
		Q.pop();

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

	for (uint i = 2; i <= V; ++i)
	{
		if (dist[i])
			fout << dist[i] - 1 << ' ';
		else
			fout << "0 ";
	}
}

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);
}