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

using namespace std;

struct arc {
	int sursa;
	int dest;
	int cost;
};

const int INF = 60000000;

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

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

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < edges.size(); j++) {
			if (dist[edges[j].dest] > dist[edges[j].sursa] + edges[j].cost) {
				dist[edges[j].dest] = dist[edges[j].sursa] + edges[j].cost;
			}
		}
	}

	for (int i = 2; i <= N; i++) {
		if (dist[i] == INF) {
			out << 0 << " ";
		} else {
			out << dist[i] << " ";
		}
	}
	out << "\n";

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