#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define INFINIT 10000


typedef struct _VECIN {
	int node;
	int cost;
}VECIN, *PVECIN;

int n, m;
int distanta[50002];
vector <VECIN> muchii[50002];
queue <int> noduri;
bool inQueue[50002];



ifstream f("dijkstra.in");
ofstream q("dijkstra.out");

void BellmanFord(vector<VECIN> muchii[50002], int sursa);

int main() {
	f >> n >> m;
	int x;
	VECIN c;
	for (int i = 0; i < m; i++) {
		f >> x >> c.node >> c.cost;
		muchii[x].push_back(c);
	}
	BellmanFord(muchii, 1);

	f.close();
	q.close();
	return 0;
}

void BellmanFord(vector<VECIN> muchii[50002], int sursa) {

	for (int i = 0; i <= n; i++) {
		distanta[i] = INFINIT;
		inQueue[i] = false;
	}

	distanta[sursa] = 0;
	noduri.push(sursa);
	int nodCurent;
	VECIN vc;

	while (!noduri.empty()) {
		nodCurent = noduri.front();
		noduri.pop();
		inQueue[nodCurent] = false;
		for (size_t i = 0; i < muchii[nodCurent].size(); i++) {
			vc = muchii[nodCurent][i];
			if (distanta[vc.node] > distanta[nodCurent] + vc.cost) {
				if (!inQueue[nodCurent]) noduri.push(vc.node);
				distanta[vc.node] = distanta[nodCurent] + vc.cost;
			}
		}
	}


	for (int i = 2; i <= n; i++) {
		if (distanta[i] == INFINIT) distanta[i] = 0;
		q << distanta[i] << " ";
	}

}