#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair
#define pb push_back

using namespace std;

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

const int N=51000;
const int INF=2147483647;

typedef pair <int,int> pereche;

vector < pereche > edge[N];
priority_queue < pereche, vector<pereche>, greater <pereche> > heap; // bag in heap distanta tentativa si nodul 

bool visited[N];
int dist[N];

int n,m;

void read(){
	int i,x,y,c;
	in>>n>>m;
	for(i=1;i<=m;++i){
		in>>x>>y>>c;
		edge[x].pb(mp(c,y));
	}
	for(i=1;i<=n;++i)
		dist[i]=INF;
}

void solve(){
	int i,j,vis=1,x;
	pereche muchie;
	heap.push(mp(0,1));
	while(!heap.empty()){
		x=heap.top().second; // x e nodul curent din varful cozii		
		if(visited[x]==1){
			heap.pop();
			continue;
		}
		dist[x]=heap.top().first; // altfel aceasta e cea mai buna distanta
		visited[x]=1;
		heap.pop();
		for(i=0;i<edge[x].size();++i){
			muchie=edge[x][i];
			if(dist[x]+muchie.first<dist[muchie.second]){
				dist[muchie.second]=dist[x]+muchie.first;
				heap.push(mp(dist[x]+muchie.first,muchie.second));
			}
		}
	}
}

void print(){
	int i;
	for(i=2;i<=n;++i){
		out<<dist[i]<<" ";
	}
}

int main(){
	read();
	solve();
	print();
	return 0;
}