#include<fstream>
#define MAXN 50001
#define inf 1<<30

using namespace std;

int d[MAXN],h[MAXN],poz[MAXN];
int n,m,k;

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

struct graf
{
	int nod,cost;
	graf *next;
};

graf *a[MAXN];

void read()
{
	int i,x,y,z;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		graf *q=new graf;
		q->nod=y;
		q->cost=z;
		q->next=a[x];
		a[x]=q;
	}
}

void swap(int x,int y)
{
	int aux=h[x];
	h[x]=h[y];
	h[y]=aux;
}

void upheap(int i)
{
	while(i>1 && d[h[i/2]]>d[h[i]])
	{
		poz[h[i/2]]=i;
		poz[h[i]]=i/2;
		swap(i/2,i);
		i=i/2;
	}
}

void downheap(int i)
{
	int stg,dr,max=i;
	stg=2*i;
	dr=2*i+1;
	if(stg<k && d[h[stg]]<d[h[i]])
		max=stg;
	if(dr<k && d[h[dr]]<d[h[max]])
		max=dr;
	if(max!=i)
	{
		poz[h[i]]=max;
		poz[h[max]]=i;
		swap(max,i);
		downheap(max);
	}
}

void dijkstra_heap()
{
	int i;
	for(i=2;i<=n;i++)
	{
		d[i]=inf;
		poz[i]=-1;
	}
	h[1]=1;
	poz[1]=1;
	k++;
	while(k)
	{
		int min=h[1];
		swap(1,k);
		poz[h[1]]=1;
		k--;
		downheap(1);
		graf *q=a[min];
		while(q)
		{
			if(d[q->nod]>d[min]+q->cost)
			{
				d[q->nod]=d[min]+q->cost;
				if(poz[q->nod]!=-1)
					upheap(poz[q->nod]);
				else
				{
					h[++k]=q->nod;
					poz[h[k]]=k;
					upheap(k);
				}
			}
			q=q->next;
		}
	}
}


int main()
{
	read();
	dijkstra_heap();
	for(int i=2;i<=n;i++)
	{
		if(d[i]==inf)
			out<<"0"<<" ";
		else
			out<<d[i]<<" ";
	}
	out<<"\n";
	return 0;
}