#include <bits/stdc++.h>

using namespace std;

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

int n,m,a,b,c;

const int DMAX=50005;

vector < pair <int, int> > 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(int i=2; i<=n; i++){
		if(dist[i]!=INT_MAX){
			fout<<dist[i]<<" ";
		}else{
			fout<<"0 ";
		}
	}
}
bool vizitat[DMAX];

priority_queue < pair <int,int> , vector < pair <int,int> >, greater < pair <int,int > > > q;

int s, ngh, cost;
void dijkstra(int nod){
	for(int i=1; i<=n; i++){
		dist[i]=INT_MAX;
	}
	dist[nod]=0;
	q.push(make_pair(0,nod));
	while(!q.empty()){
		s=q.top().second;
		q.pop();
			for(unsigned 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;
					q.push(make_pair(dist[ngh],ngh));
				}
			}
	}
}
int main(){
	read();
	dijkstra(1);
	print();
}