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

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

const int maxn = 50005;
const int INF = 0x3f3f3f3f;

struct nod
{
    int w;
    int dis;
}one;

int n,m;
vector< nod > G[maxn];
int Dmin[maxn];

void ReadData() {

	f >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c;

		f >> a >> b >> c;
		one.w=b;
		one.dis=c;
		G[a].push_back(one);
	}
}

void Solve() {
	bool InQueue[maxn];
	queue<int> Q;

	memset(Dmin, INF, sizeof(Dmin));
	memset(InQueue, false, sizeof(InQueue));

	Dmin[1] = 0;
	Q.push(1);
	InQueue[1] = true;

	while (!Q.empty()) {
		int k= Q.front();
		Q.pop();
		InQueue[k] = false;

		for (vector< nod >::iterator it = G[k].begin(); it != G[k].end(); ++it)
			if (Dmin[k] + it->dis < Dmin[it->w]) {
				Dmin[it->w] = Dmin[k] + it->dis;
				if (!InQueue[it->w]) {
					Q.push(it->w);
					InQueue[it->w] = true;
				}
			}
	}
}

void WriteData() {

	for (int i = 2; i <= n; ++i)
		g << (Dmin[i] < INF ? Dmin[i] : 0) << " ";
}

int main() {
	ReadData();
	Solve();
	WriteData();
}