#include <stdio.h>
#include <vector>
#include <set>

using namespace std;

FILE *f,*s;

int i,j,k,l,m,n;

int v3[50100];

vector<int> v1[50100],v2[50100];

set < pair <int,int> > p;

void Dijkstra()
{
	for(i=2;i<=n;i++) 
		v3[i]=2000000000;
	
	p.insert(make_pair(0,1));
	
	int val, x;
	
	while( p.size() > 0 )
	{
		val=(*p.begin()).first;
		x=(*p.begin()).second;

		p.erase(*p.begin());

		for(i=0;i<v1[x].size();i++)
			if(v3[v1[x][i] ]>val+v2[x][i])
				v3[v1[x][i]]=val+v2[x][i], p.insert(make_pair(v3[v1[x][i]],v1[x][i]));
	}
}

int main()
{
	f=fopen("dijkstra.in","r");
	s=fopen("dijkstra.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	
	for(i=1;i<=n;i++)
	{
		int a,b,c;
		
		fscanf(f,"%d %d %d",&a,&b,&c);
		
		v1[a].push_back(b);
		v2[a].push_back(c);
	}
	
	Dijkstra();
	
	for(i=2;i<=n;i++)
	{
		if(v3[i]==2000000) 
			fprintf(s,"0 ");
		else
			fprintf(s,"%d ",v3[i]);
	}
	
	fclose(s);
	
	return 0;
}