#include <cstdio>
#include <vector>
#include <fstream>
#include <set>

using namespace std;

#define N 50005
#define inf 1<<30

struct nod{
	int varf;
	int cost;
	};

vector<nod>  v[N];
set< pair < int , int > > s;
int n,m;

void dijkstra (int start){
	
	vector<int> d(n+1,inf);
	s.insert(make_pair(0,start));
	while(s.size()>0){
		int val=(*s.begin()).first, x=(*s.begin()).second;
		s.erase(*s.begin());
		for(vector<nod>::iterator it=v[x].begin();it<v[x].end();++it)
			if(d[(*it).varf]>val+(*it).cost){
				d[(*it).varf]=val+(*it).cost;
				s.insert(make_pair(d[(*it).varf],(*it).varf));
				}
		}
	for(int i=2;i<=n;++i)
	printf("%d ",d[i]==inf?0:d[i]);
	}

int main ()
{
	
	ifstream in ("dijkstra.in");
	freopen ("dijkstra.out","w",stdout);
	in>>n>>m;
	for(;m;--m){
		nod x;
		int i;
		in>>i>>x.varf>>x.cost;
		v[i].push_back(x);
		}
	dijkstra (1);
	printf("\n");
	
	return 0;}