#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 b,c;
	graf *next;
};

graf *a[MAXN];

void citire()
{
	in>>n>>m;
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		graf *q=new graf;
		q->b=y;
		q->c=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 increase_key(int i,int key)
{
	h[i]=key;
	while(i>1 && d[h[i/2]]>d[h[i]])
	{
		swap(i/2,i);
		i=i/2;
	}
}

void insert(int key)
{
	poz[key]=1;
	k++;
	increase_key(k,key);
}

void heapify(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)
	{
		swap(max,i);
		heapify(max);
	}
}

void eliminare()
{
	h[1]=h[k];
	k--;
	heapify(1);
}

void dijkstra()
{
	int i;
	for(i=1;i<=n;i++)
	{
		d[i]=inf;
		poz[i]=0;
	}
	d[1]=0;
	poz[1]=1;
	h[1]=1;
	k++;
	while(k>0)
	{
		int min=h[1];
		eliminare();
		poz[1]=0;
		graf *q=a[min];
		while(q)
		{
			if(d[q->b]>d[min]+q->c)
				d[q->b]=d[min]+q->c;
			if(poz[q->b]==0)
				insert(q->b);
			q=q->next;
		}
	}
}


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