/*
	Bellman-Ford-Moore algorithm.
*/

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

using namespace std;

#define N 50001
#define oo 0x3f3f3f3f

int n, m, d[N];
vector<pair<int, int> > L[N];

void readData() {
	ifstream fin("dijkstra.in", ios::in);

	// number of nodes
	fin>>n;

	// number of edges
	fin>>m;

	for (int i=1; i<=m; i++) {
		int x, y, c;

		fin>>x>>y>>c;
		L[x].push_back(make_pair(y, c));
	}
}

void BellmanFordMoore() {
	queue<int> q;
	int in_queue[N];

	memset(d, oo, sizeof(d));
	d[1]=0;
	memset(in_queue, 0, sizeof(in_queue));

	q.push(1); // push source in deque
	in_queue[1]=1;

	while (!q.empty()) {
		int v=q.front();
		q.pop();
		in_queue[v]=0;
		
		for (int j=0; j<L[v].size(); j++) {
			int w=L[v][j].first;
			int c=L[v][j].second;
		
			// relax edge
			if (d[w]>d[v]+c) {
				d[w]=d[v]+c;
					
				// maintaint edges in deque whose distance have changed
				if (!in_queue[w]) {
					in_queue[w]=1;
					q.push(w);
				}
			}
		}
	}
}

void showDistances() {
	ofstream fout("dijkstra.out", ios::out);

	for (int i=2; i<=n; i++)
		fout<<(d[i] < oo ? d[i] : 0)<<" ";
}

int main() {
	readData();
	
	BellmanFordMoore();

	showDistances();

	return 0;
}