#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#include <utility>
#define dim 50001
#define inf 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;

struct comp{
	bool operator() (const pii &a ,const pii &b)
	{
		return (a.second<b.second);
	}	
};


priority_queue<pii, vector<pii> ,comp> H;
vector<pii> v[dim];
int a,b,c,n,m,dist[dim],u,d,distn,i;


void Dijkstra(){

	memset(dist,inf,sizeof(dist));
	dist[1]=0;
	
	H.push(make_pair(1,0));
	while(!H.empty()){
		u=H.top().first;
		d=H.top().second;
		H.pop();
	
		for(i=0;i<int(v[u].size());i++){
			distn=d+v[u][i].second;
			if(distn<dist[v[u][i].first]){
				dist[v[u][i].first]=distn;
				H.push(make_pair(v[u][i].first,distn));
			}
		}
	}
}


int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>a>>b>>c;
		v[a].push_back(make_pair(b,c));
	}

	Dijkstra();

	for(i=2;i<=n;i++)
	g<<((dist[i]!=inf)?dist[i]:0)<<" "; 
}