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

using namespace std;

struct muc{
	int a, v;
};

struct nod{
	int a, v;
	bool operator<(const nod &rhs)const{
		if(v != rhs.v){
			return v < rhs.v;
		}
		return a < rhs.a;
	}
};

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

int n, m;
set<nod> se;

vector<muc> gra[50041];
bool vi[50041];
int va[50041];

void addme(nod x){
	if(!vi[x.a] && (x.v < va[x.a] || va[x.a] == 0)){
		if(va[x.a] != 0){
			se.erase({x.a, va[x.a]});
		}
		se.insert(x);
		va[x.a] = x.v;
	}
}

void drijkstra(){
	se.insert({1, 0});
	while(!se.empty()){
		nod x = *se.begin();
		se.erase(se.begin());
		vi[x.a] = 1;
		
		vector<muc> &v = gra[x.a];
		for(auto y : v){
			addme({y.a, va[x.a]+y.v});
		}
	}
}

int main(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a;muc x;
		fin >> a >> x.a >> x.v;
		gra[a].push_back(x);
	}
	drijkstra();
	for(int i = 2; i <= n; ++i){
		fout << va[i] << " ";
	}
	return 0;
}