#include<stdio.h>

#define max 50002
#define inf 1<<30

int n,m,k;

int heap[max],nodes[max],pos[max],l,hl;
bool visited[max];
struct node
{
	int dest,cost;
	node* next;
} *roads[250005];


void push(int x,int y,int z)
{
	node *p=new node;
	p->dest=y;
	p->cost=z;
	p->next=roads[x];
	roads[x]=p;
}
void swap(int x, int y)
{
    int t = heap[x];
    heap[x] = heap[y];
    heap[y] = t;
}
 
void upheap(int who)
{
      int aux;
	  while(who/2 && nodes[heap[who]]<nodes[heap[who/2]] )
	  {
		  aux=heap[who];
		  heap[who]=heap[who/2];
		  heap[who/2]=aux;

		  pos[heap[who]]=who/2;
		  pos[heap[who/2]]=who;
		  who/=2;
	  }
}
void downheap(int what)
{
	int f;
	while( what<=k )
	{
		f=what;
		if ( (what<<1) <=k )
		{
			f=what<<1;
			if(f+1<=k)
				if(nodes[heap[f+1]]<nodes[heap[f]])
					++f;
		}
		else
			return;
		if(nodes[heap[what]] > nodes[heap[f]])
		{
			pos[heap[what]]=f;
			pos[heap[f]]=what;
				swap(what,f);
			what=f;
		}
		else
			return;
	}
}

void dijkstra()
{
	for(int i=2;i<=n;i++)
		nodes[i]=inf,pos[i]=-1;
	pos[1]=1;
	heap[++k]=1;

	while(k)
	{
		int min=heap[1];
		swap(1,k);
		pos[heap[1]]=1;
		--k;

		downheap(1);

		node *q=roads[min];

		while(q)
		{
			if(nodes[q->dest] > nodes[min] + q->cost)
			{
				nodes[q->dest]=nodes[min] + q->cost;

                if(pos[q->dest] !=-1)
					upheap(pos[q->dest]);
				else
				{
					heap[++k]=q->dest;
					pos[heap[k]]=k;
					upheap(k);
				}
			}
			q=q->next;
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	scanf("%d%d",&n,&m);
	hl=1;
	int x,y,z;

	for(int i=1;i<=m;i++) 
	{
		scanf("%d%d%d",&x,&y,&z);
		push(x,y,z);
	}

    
   dijkstra();

	for(int i=2;i<=n;i++)
	  if(nodes[i] != inf)
		printf("%d ",nodes[i]);
	  else
		  printf("0 ");
	return 0;
}