#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f

priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > heap;
int n,m;
int cost_min[50002];
vector< pair<int,int> > v[50002];

void dijkstra(int sursa)
{
  memset(cost_min,inf,sizeof(cost_min));
  heap.push( make_pair(0,sursa) );
  int nod, cost;
  while(!heap.empty())
  {
    cost = heap.top().first;
    nod = heap.top().second;
    heap.pop();
    if(cost_min[nod] != inf)
      continue;
    cost_min[nod] = cost;
    for(vector< pair<int,int> >::iterator it = v[nod].begin(); it != v[nod].end(); ++ it)
      heap.push(make_pair(it->first + cost, it->second));
  }
}

int main()
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  scanf("%d %d\n", &n, &m);
  int i, j, x, y, c;
  char s[30];
  for(i = 1; i <= m; i++)
  {
    x = y = c = 0;
    gets(s);
    for(j = 0; s[j] != ' '; j++)
      x = x * 10 + s[j] - '0';
    for(++j; s[j] !=' '; j++)
      y = y * 10 + s[j] - '0';
    for(++j; s[j] ; j++)
      c = c * 10 + s[j] - '0';
    fprintf(stderr, "%d %d %d\n", x, y, c);
    v[x].push_back(make_pair(c, y));
  }
  dijkstra(1);
  for(i = 2; i <= n; i++)
    printf("%d ",cost_min[i] != inf ? cost_min[i] : 0);
  return 0;
}