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

using namespace std;

struct arc {
public:
	arc() {}
	arc(int nod, int cost) : nod(nod), cost(cost) {}
	int nod;
	int cost;
};

class mycomparison
{
public:
	bool operator() (const arc& lhs, const arc&rhs) const
	{
		return (lhs.cost > rhs.cost); //sorteaza crescator
	}
};

typedef std::priority_queue<arc, std::vector<arc>, mycomparison> mypq_type;

int main()
{
	ifstream in; ofstream out;
	in.open("dijkstra.in"); out.open("dijkstra.out");
	int N, M, a;
	int start = 1;
	arc b;
	mypq_type pq;

	in >> N >> M;
	vector<int> dist(N + 1, 0);
	vector<bool> marked(N + 1, false);
	vector<vector<arc> > edges(N + 1, vector<arc>());
	for (int i = 0; i < M; i++) {
		in >> a >> b.nod >> b.cost;
		edges[a].push_back(b);
	}

	b.cost = 0;
	b.nod = start;
	pq.push(b);
	int marked_no = 0;

	while (!pq.empty() && marked_no < N) {
		arc elem = pq.top();
		pq.pop();
		if (marked[elem.nod])
			continue;
		vector<arc> &neigh = edges[elem.nod];
		for (int i = 0; i < neigh.size(); i++) {
			if (dist[neigh[i].nod] == 0 ||
				dist[neigh[i].nod] > elem.cost + neigh[i].cost) {
				dist[neigh[i].nod] = elem.cost + neigh[i].cost;
				pq.push(arc(neigh[i].nod, dist[neigh[i].nod]));
			}
		}
		marked[elem.nod] = true;
		marked_no++;
	}

	for (int i = 2; i <= N; i++)
		out << dist[i] << " ";
	out << "\n";

	in.close(); out.close();
	return 0;
}