#include <stdio.h>
#include <vector>
#include <utility>
#define NMax 100000
using namespace std;

const char IN[]="dijkstra.in",OUT[]="dijkstra.out";

int N,M;
vector< pair<int,int> > ad[NMax];
vector<int> dist;
int heap[NMax];
int p[NMax];

void remake(int *a,int i)
{
	int min;
	int r= 2*i+1;
	int l= 2*i;
	
	if (l<=a[0] && dist[a[l]]<dist[a[i]])
		min=l;
	else
		min=i;
	
	if (r<=a[0] && dist[a[r]]<dist[a[min]])
		r=min;
	
	if (min!=i)
	{
		int tmp;
		tmp=p[a[min]];
		p[a[min]]=p[a[i]];
		p[a[i]]=tmp;
		
		tmp=a[min];
		a[min]=a[i];
		a[i]=tmp;
		remake(a,min);
	}
}

void make(int *a)
{
	int i;
	for (i=a[0]/2;i>0;--i)
		remake(a,i);
}

void insert(int *a,int val)
{
	int i;
	++a[0];
	a[a[0]]=val;
	p[val]=a[0];
	
	for (i=a[0];i>1 && dist[a[i]]<dist[a[i/2]];i/=2)
	{
		int tmp;
		
		tmp=p[a[i]];
		p[a[i]]=p[a[i/2]];
		p[a[i/2]]=p[a[i]];
		
		tmp=a[i];
		a[i]=a[i/2];
		a[i/2]=tmp;
	}
}

void del(int *a,int x)
{
	int tmp,pr=p[x];
	
	tmp=p[x];
	p[x]=p[a[a[0]]];
	p[a[a[0]]]=tmp;
	
	tmp=a[pr];
	a[pr]=a[a[0]];
	a[a[0]]=tmp;
	
	a[a[0]]=0;
	--a[0];
	
	remake(a,pr);
	p[x]=0;
}

void Dijkstra()
{
	int i,x;
	vector< pair<int,int> >::iterator it;
	dist.assign(N,-1);
	dist[0]=0;
	insert(heap,0);
	
	for (i=0;i<N;++i)
	{
		x=heap[1];
		
		for ( it= ad[x].begin() ; it<ad[x].end(); ++it)
			if ( dist[it->first]==-1 || dist[it->first]> it->second+dist[x])
			{
				dist[it->first]= it->second+dist[x];
				if (p[it->first]>0)
					del(heap,it->first);
				insert(heap,it->first);
			}
		del(heap,heap[1]);
	}
	
}

int main()
{
	int i,x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<N;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		ad[x-1].push_back(make_pair(y-1,c));
	}
	fclose(stdin);
	
	Dijkstra();
	
	freopen(OUT,"w",stdout);
	for (i=1;i<N;++i)
		printf("%d ",dist[i]);
	printf("\n");
	fclose(stdout);
	
	return 0;
}