#include <bits/stdc++.h>

using namespace std;

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

int n,m,a,b,c;

const int DMAX=500005;
const int oo=2000000;

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

void read(){
	fin>>n>>m;
	for(int i=1; i<=m; i++){
		fin>>a>>b>>c;
		g[a].push_back(make_pair(b,c));
	}
}
void print(){
	for(int i=2; i<=n; i++){
		fout<<dist[i]<<" ";
	}
}
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;

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

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