#include <stdio.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

set <pair <int,int> > s;
set <pair <int,int> >::iterator it;
//set <int>::iterator it1;
vector <int> v[50010];
vector <int> c[50010];

int n,m,a,b,i,cc,j,dmin[50010];

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d %d %d",&a,&b,&cc);
		v[a].push_back(b);
		c[a].push_back(cc);
	}
	for(i=2;i<=n;i++){
		//s.insert(make_pair(1000000000,i));
		dmin[i]=1000000000;
	}
	s.insert(make_pair(0,1));
	dmin[1]=0;
	for(i=2;i<=n;i++){
		it=s.begin();
		for(j=0;j<c[it->second].size();j++){
			if(dmin[v[it->second][j]]>dmin[it->second]+c[it->second][j]){
				s.erase(make_pair(dmin[v[it->second][j]],v[it->second][j]));
				dmin[v[it->second][j]]=dmin[it->second]+c[it->second][j];
				s.insert(make_pair(dmin[v[it->second][j]],v[it->second][j]));
			}
		}
		s.erase(*it);
	}
	for(i=2;i<=n;i++){
		if(dmin[i]<1000000000){
			printf("%d ",dmin[i]);
		}else{
			printf("0 ");
		}
	}
	return 0;
}