#include<stdio.h>
#include<vector>
#define maxn 50005
#define MAXX 999999999

using namespace std;

int n,m,d[maxn],poz[maxn],x[maxn],nh,r=1;

vector <int > v[maxn],vc[maxn];


void cit()
{
	int i,x,y,cc;

	scanf("%d %d",&n,&m);

	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&cc);

		v[x].push_back(y);
		vc[x].push_back(cc);
	}
}




void swap(int i,int j)
{
	int aux;

	aux=x[i];
	x[i]=x[j];
	x[j]=aux;

	poz[x[i]]=i;
	poz[x[j]]=j;
}






void heapup(int k)
{
	int i;

	if(k<=1)
		return ;

	i=k/2;

	if(d[x[k]]<d[x[i]])
	{
		swap(i,k);
		heapup(i);
	}
}




void buildh(int k)
{
	int i;

	for(i=1;i<=n;i++)
		heapup(i);
}




void heapdw(int r,int k)
{
	int st,dr,i;


	if(2*r<=k)
	{
		st=x[2*r];

		if(2*r+1<=k)
			dr=x[2*r+1];
		else
			dr=-2;

	if(d[st]<d[dr] || dr==-2)
		i=2*r;
	else
		i=2*r+1;


	if(d[x[r]]>d[x[i]])
	{
		swap(r,i);
		heapdw(i,k);
	}
	else
		return ;
    }
}





int scoate_heap()
{
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	heapdw(1,nh);

	return x[nh+1];
}




void dijkstra()
{
	int i,p,aux;

	for(i=1;i<=n;i++)
	{
		d[i]=MAXX;
		x[i]=i;
		poz[i]=i;
	}


	d[r]=0;
	nh=n;

	buildh(n);


	while(nh>0)
	{
		p=scoate_heap();
		aux=v[p].size();

		for(i=0;i<aux;i++)
		{
			if(d[v[p][i]]>d[p]+vc[p][i] && poz[v[p][i]])
			{
				d[v[p][i]]=d[p]+vc[p][i];

				heapup(poz[v[p][i]]);
			}
		}
	}
}





void afis()
{
	int i;

	for(i=1;i<=n;i++)
		if(i!=r)
		{
		 if(d[i]<MAXX)
			printf("%d ",d[i]);
		else
			printf("0");
		}
}





int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);


	cit();
	dijkstra();
	afis();


	fclose(stdin);
	fclose(stdout);
	return 0;
}