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

using namespace std;

#define PINF (1<<30)

struct Muchie {
	int vecin;
	int cost;
};

vector<Muchie>muchii[50002];
queue<int>Q;
bitset<50002>InQ;
vector<int>distante(50002, PINF);
int n, m;

void initAndRead() {
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		Muchie temp;
		int a, b, c;
		fin >> a >> b >> c;
		temp.vecin = b;
		temp.cost = c;
		muchii[a].push_back(temp);
	}
	fin.close();
}

void dijkstra(int start) {

	distante[start] = 0;
	Q.push(start);
	InQ[start] = 1;
	while (!Q.empty()) {
		int nod = Q.front();
		Q.pop();
		InQ[nod] = 0;
		for (vector<Muchie>::iterator it = muchii[nod].begin(); it != muchii[nod].end(); ++it) {
			if (distante[nod] + it->cost < distante[it->vecin]) {
				distante[it->vecin] = distante[nod] + it->cost;
				if (!InQ[it->vecin]) {
					Q.push(it->vecin);
					InQ[it->vecin] = 1;
				}
			}
		}
	}
}

void scrieDate() {
	ofstream fout("dijkstra.out");
	for (int i = 2; i < n + 1; ++i)
		fout << (distante[i] == PINF ? 0 : distante[i]) << " ";
	fout << '\n';
	fout.close();
}

int main() {
	initAndRead();
	dijkstra(1);
	scrieDate();
	return 0;
}