#include <fstream.h>
#include <vector>
#include <list>
#include <queue>

using namespace std;
int n,m,d[50000];
const long inf = 100000000;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
vector<list<pair<int,int> > >v;
list<pair<int,int> >::iterator it;
queue<int> Q;

void citire(){
	fi>>n;
	fi>>m;
	v.resize(n+1);
	int i,j,k,c;
	for(i=1;i<=n;i++)
		v[i].push_back(pair<int,int>(0,0));
	for(k=1;k<=m;k++){
		fi>>i;
		fi>>j;
		fi>>c;
		v[i].push_back(pair<int,int>(j,c));
	}
	fi.close();
}

void afisare(){
	int i;
	for(i=2;i<=n;i++)
		fo<<d[i]<<" ";
	fo<<'\n';
	fo.close();
}

void dijkstra(){
	int i,nod;
	for(i=2;i<=n;i++)
		d[i]=inf;
	Q.push(1);
	
	while(!Q.empty()){
		nod = Q.front();
		Q.pop();
		
		for(it=v[nod].begin();it!=v[nod].end();++it)
			if(d[it->first]>d[nod]+it->second){
				d[it->first]=d[nod]+it->second;
				Q.push(it->first);
			}
	}
	for(i=2;i<=n;i++)
		if(d[i]==inf)
			d[i]=0;
}	


int main(){
	citire();
	dijkstra();
	afisare();
	return 0;
}