#include <iostream>
#include <fstream>
#include <set>
#include <vector>

#define MAXN 50010
#define MAXM 250100
#define INF 1000000000

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

//int H[MAXN],poz[MAXN];

int N,M;
struct Edge {
	int at;
	int cost;
};
struct Node {
	int dist;
	vector<Edge> Adj;
};
Node V[MAXN];
struct CompareNodes {
	bool operator() (const int& A, const int& B) const {
		return V[A].dist <= V[B].dist;
	}
};
set<int,CompareNodes> s;
/*
void siftUp(int x) {
	while (x/2 && V[H[x]].dist < V[H[x/2]].dist) {
		swap(H[x],H[x/2]);
		poz[H[x]] = x;
		poz[H[x/2]] = x/2;
		x /= 2;
	}
}

void siftDown(int x) {
	int left,right,minInd;
	left = x * 2;
	right = x * 2 + 1;
	if (left > H[0]) return;
	minInd = left;
	if (right <= H[0]) {
		if (V[H[minInd]].dist < V[H[right]].dist) {
			minInd = right;
		}
	}
	swap(H[x],H[minInd]);
	poz[H[x]] = x;
	poz[H[minInd]] = minInd;
	
	siftDown(minInd);
}

int removeTop() {
	if (H[0] == 0) return -1;
	else H[1] = H[H[0]];
	H[0]--;
	siftDown(1);
}
*/
void read_f() {
	int i,x,y,c;
	Edge tmp;
	fin >> N >> M;
	for (i=0;i<M;++i) {
		fin >> x >> y >> c;
		x -= 1;
		y -= 1;
		tmp.at = y;
		tmp.cost = c;
		V[x].Adj.push_back(tmp);
	}
	for (i=0;i<N;++i) V[i].dist = INF;
	
	V[0].dist = 0;
	s.insert(0);
	
	fin.close();
}

void dijktra() {
	int x,i;
	while (!s.empty()) {
		x = *s.begin();
		s.erase(s.begin());
		for (i=0;i<V[x].Adj.size();++i) {
			if (V[V[x].Adj[i].at].dist > V[x].dist + V[x].Adj[i].cost) {
				V[V[x].Adj[i].at].dist = V[x].dist + V[x].Adj[i].cost;
				s.insert(V[x].Adj[i].at);
			}
		}
	}
}

void write_f() {
	int i;
	for (i=1;i<N;++i)
		fout << ((V[i].dist >= INF)?0:V[i].dist) << " ";
	fout << "\n";
	fout.close();
}

int main() {
	read_f();
	dijktra();
	write_f();
	return 0;
}