#include <fstream>
#include <vector>

#define oo 1 << 30
#define NMax 50001

using namespace std;

int N, M, x, y, c, dist[NMax];
bool changed;
vector < pair <int, int>> G[NMax];

int main()
{
	int i, j;

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

	fin >> N >> M;
	
	for (i = 2; i <= N; i++) {
		dist[i] = oo;
	}

	for (i = 1; i <= M; i++) {
		fin >> x >> y >> c;

		G[x].push_back({ y, c });
	}

	for (i = 1; i <= M - 1; i++) {
		changed = false;
		for (j = 1; j <= N; j++) {
			for (auto node : G[j]) {
				if (node.second + dist[j] < dist[node.first]) {
					dist[node.first] = node.second + dist[j];
					changed = true;
				}
			}
		}
		if (!changed) {
			break;
		}
	}

	for (i = 2; i <= N; i++) {
		fout << dist[i] << " ";
	}

	fin.close();
	fout.close();
}