#include <bits/stdc++.h>

using namespace std;

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

int n,m,a,b,c,dist[50010];
vector<pair<int,int> > v[50010];
bitset<50010> in;

priority_queue<pair<int,int>> q;

int main(){
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>a>>b>>c;
		v[a].push_back({b,c});
	}
	memset(dist,127,sizeof(dist));
	dist[1]=0;
	for(int i=1;i<=n;i++)
		q.push({-dist[i],i}),in[i]=1;
	while(q.size()){
		pair<int,int> aux=q.top();q.pop();
		if(dist[aux.second]!=-aux.first)continue;
		int poz=aux.second;in[poz]=0;
		for(auto it:v[poz])
			if(in[it.first]&&dist[it.first]>dist[poz]+it.second){
				dist[it.first]=dist[poz]+it.second;
				q.push({-dist[it.first],it.first});
			}
	}
	for(int i=2;i<=n;i++)
		if(dist[i]==2139062143)
			g<<"0 ";
		else
			g<<dist[i]<<' ';
}