#include<cstdio>

#define inf 0x3f3f3f3f
#define nmax 50010

struct graph {
	int cost, node;
	graph *next;
	};

graph *v[nmax];
int n, m, d[nmax], heap[nmax], pheap[nmax], nheap;

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

void addh(int child)
{
  int father;
	while(child > 1)
	{
		father = child/2;
		if( d[ heap[father]] > d[ heap[child] ] )
		{
			swap(child, father);
			pheap[ heap[child]] = father;
			pheap[ heap[father]] = child;
			child = father;
		}
		else
			return;
	}
}

void removeh()
{
  int child, father = 1;
  while(father * 2 <= nheap)
  {
    child = father * 2;
    if(d[ heap[child]] < d[ heap[child+1] ])
      child++;
    if(d[ heap[father] ] > d[ heap[child] ])
      {
				swap(father, child);
				pheap[ heap[child] ] = father;
				pheap[ heap[father] ] = child;
				father = child;
      }
    else
      return;
  }
}


void dijkstra()
{
	int i, min;
	graph *t;

	for(i=2; i<=n; i++)
		{
			d[i] = inf;
			pheap[i] = -1;
		}
	pheap[1] = 1;
	heap[1] = 1;
	nheap = 1;

	while(nheap)
	{
		min = heap[1];
		swap(1, nheap);
		nheap--;
		pheap[ heap[1] ] = 1;
		removeh();

		t = v[min];

		while(t)
		{
			if(d[t->node] > d[min] + t->cost)
			{
				d[t->node] = d[min] + t->cost;
				if(pheap[t->node] != -1)
					addh(pheap[t->node]);
				else
				{
					heap[++nheap] = t->node;
					pheap[ heap[nheap] ] = nheap;
					addh(nheap);
				}
			}
			t = t->next;
		}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);	
	scanf("%d %d", &n, &m);
	int i, x, y, z;
	graph *q;
	for(i=1; i<=m; i++)
	{
			scanf("%d %d %d", &x, &y, &z);
			q = new graph;
			q->node = y;
			q->cost = z;
			q->next = v[x];
			v[x] = q;
	}
	dijkstra();
	for(i=2; i<=n; i++)
		printf("%d ", d[i]);
	printf("\n");
	return 0;
}