#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;

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


void cit()
{
	int i,p1,p2,cc;

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

     r=1;

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

		v[p1].push_back(p2);
		vc[p1].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 heap_dw(int k)
{
    int i=2*k;

    if(i<=nh)
    {
        if(i+1<=nh && d[x[i+1]]<d[x[i]])
             i++;

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




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

	return x[nh+1];
}




void dijkstra()
{
	int p;
	unsigned int i;

	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();
		heap_dw(1);


		for(i=0;i<v[p].size();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=2;i<=n;i++)
		 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;
}