#include <bits/stdc++.h>

using namespace std;

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

int n,m,a,b,c;

const int DMAX=50010;
const int oo=2147483647;

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

void read(){
	fin>>n>>m;
	for(int 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()(int x, int y){
		if(dist[x]>dist[y]){
			return true;
		}
		return false;
	}
};

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

int s, ngh, cost;
void dijkstra(int nod){
	for(int i=1; i<=n; i++){
		dist[i]=oo;
	}
	dist[nod]=0;
	q.push(nod);
	while(!q.empty()){
		s=q.top();
		q.pop();
		vizitat[s]=true;
		for(int j=0; j<graf[s].size(); j++){
			ngh=graf[s][j].first;
			cost=graf[s][j].second;
			if(dist[ngh]>dist[s]+cost){
				dist[ngh]=dist[s]+cost;
				if(vizitat[ngh]==false){
					q.push(ngh);
				}
			}
		}
	}

}
int main(){
	read();
	dijkstra(1);
	print();
}