#include<fstream>
#define MAXX 999999999
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod{int inf,c; nod *urm;};
nod *l[50002];

int d[50002],x[50002],poz[50002],t[50002],n,m,nh,r;



void add(int p1,int p2,int cost)
{
	nod *q;

	q=new nod;
	q->inf=p2;
	q->c=cost;

	q->urm=l[p1];
	l[p1]=q;
}




void citire()
{
	int p1,p2,cost,i;

	fin>>n>>m;
	r=1;

	for(i=1;i<=m;i++)
	{
		fin>>p1>>p2>>cost;
		add(p1,p2,cost);
	}

	fin.close();
}




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

	return x[nh+1];
}




void Dijkstra()
{
	int i,k;
	nod *p;

	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)
	{
		k=scoate_heap();

		p=l[k];

		while(p)
		{
			if(d[p->inf] > d[k]+p->c && poz[p->inf])
			{
				d[p->inf]=d[k]+p->c;
                t[p->inf]=k;

				HeapUP(poz[p->inf]);
			}

			p=p->urm;
		}
	}
}





void afis()
{
	int i;

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

	fout.close();
}




int main()
{
	citire();
	Dijkstra();
	afis();

	return 0;
}