#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;
vector< nod > a[maxn];

int n,m,k,i,dis[maxn],j,x,y,z;

bool been[maxn];

queue<int> Q;

void ReadData() {

	f>>n>>m;
	for (i=1;i<=m;++i) {

		f >> x >> y >> z;
		one.w=y;
		one.dis=z;
		a[x].push_back(one);
	}
}

void Solve() {

	memset(been, false, sizeof(been));
	memset(dis, INF, sizeof(dis));

	dis[1] = 0;
	Q.push(1);
	been[1] = true;

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

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

void WriteData() {

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

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