#include <fstream>
#include <vector>
#define DIM 50005

using namespace std;
 //Compiler version g++ 6.3.0

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

int c[DIM], v[DIM], l[DIM], nod, k, n, m, x, p, u, y, z, i;

vector < pair <int, int> > L[DIM];

int main()
{
	fin >> n >> m;
	for (int i=1; i<=m; i++){
		fin >> x >> y >> z;
		L[x].push_back({y, z});
	}
	p=u=1;
	c[1]=1;
	v[1]=1;
	while (p <= u){
		nod = c[p];
		for (i=0; i<L[nod].size(); i++){
			k = L[nod][i].first;
			if (v[k] == 0){
				v[k] = 1;
				c[++u] = k;
				l[k] = l[nod] + L[nod][i].second;
			}
		}
		p++;
	}
	for (i=2; i<=n; i++){
		fout << l[i] << " ";
	}
	return 0;
}