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

const int N = 50000;
const int INF = 0x3f3f3f3f;

int n,m;
vector< pair<int,int> > g[N];
int d[N];
int r[N];
vector<int> rev[N];

class dist_cmp {
public:
	bool operator() ( int a, int b ) { return d[a] < d[b]; };
};

void dijkstra() {
	multiset<int, dist_cmp> s;
	d[0] = 0;
	for (int i = 1; i < n; ++i) d[i] = INF;
	for (s.insert(0); !s.empty(); s.erase(s.begin())) {
		int c = *s.begin();
		vector< pair<int,int> > &cg = g[c];
		for (int i = 0; i < cg.size(); ++i) {
			int nd = d[c] + cg[i].second;
			if (d[cg[i].first] > nd) {
				d[cg[i].first] = nd;
				s.insert(cg[i].first);
			}
		}
	}
}

int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> n >> m;
	for (int i = 0, a, b, c; i < m; ++i) {
		fin >> a >> b >> c;
		g[a-1].push_back(make_pair(b-1,c));
	}
	dijkstra();
	for (int i = 1; i < n; ++i) fout << (d[i] == INF) ? 0 : d[i] << ' ';
	fout << '\n';
	return 0;
}