#include <bits/stdc++.h>

using namespace std;

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

int n,m,a,b,c;

const long long DMAX=50010;
const long long oo=20000000;

vector < pair <int, int> > graf[DMAX];
int dist[DMAX];

void read(){
	fin>>n>>m;
	for(long long i=1; i<=m; i++){
		fin>>a>>b>>c;
		graf[a].push_back(make_pair(b,c));
	}
}
void print(){
	for(long long i=2; i<=n; i++){
		if(dist[i]!=oo){
			fout<<dist[i]<<" ";
		}else{
			fout<<"0 ";
		}
	}
}
bool vizitat[DMAX];

struct comp{
	bool operator()(long long x, long long y){
		if(dist[x]>dist[y]){
			return true;
		}
		return false;
	}
};

priority_queue <long long, vector<long long>, comp> q;

void dijkstra(long long nod){
	for(long long i=1; i<=n; i++){
		dist[i]=oo;
	}
	dist[nod]=0;

	long long ngh, s, cost;
	q.push(nod);
	while(!q.empty()){
		s=q.top();
		q.pop();
		vizitat[s]=true;
		for(unsigned long long i=0; i<graf[s].size(); i++){
			ngh=graf[s][i].first;
			cost=graf[s][i].second;
			if(dist[s]+cost<dist[ngh] && vizitat[ngh]==false){
				dist[ngh]=dist[s]+cost;
				q.push(ngh);
			}
		}
	}
}
int main(){
	read();
	dijkstra(1);
	print();
}