#include<cstdio>
#include<climits>
#include<vector>

#define nmax 50005
#define inf INT_MAX
#define cost first
#define nod second

using namespace std;

typedef pair<int, int> ii;

int n, m, num, d[nmax], h[nmax], p[nmax];
vector<ii> g[nmax];

void scan(){
  int i, a, b, c;
  scanf("%d%d", &n, &m);
  for(i = 1; i <= m; ++i){
    scanf("%d%d%d", &a, &b, &c);
    g[a].push_back(ii(c, b));
  }
}

inline void swap_(int p1, int p2){
  p[h[p1]] = p2;
  p[h[p2]] = p1;

  int aux = h[p1];
  h[p1] = h[p2];
  h[p2] = aux;
}

void upheap(int poz){
  if(poz == 1)
    return;
  if(d[h[poz]] >= d[h[poz>>1]])
    return;
  
  swap_(poz, poz>>1);

  upheap(poz>>1);
}

void downheap(int poz){
  int f1 = poz<<1, f2 = (poz<<1)+1, fmin = f1;
  if(f1 > num)
    return;
  if(f2 <= num && d[h[f2]] < d[h[f1]])
    fmin = f2;
  if(d[h[fmin]] >= d[h[poz]])
    return;

  swap_(poz, fmin);

  downheap(fmin);
}

void dijkstra(){
  int i, top;
  for(i = 2; i <= n; ++i)
    d[i] = inf;
  
  num = 1;
  h[1] = 1;
  p[1] = 1;
  while(num){
    top = h[1];
    h[1] = h[num];
    --num;
    downheap(1);
    for(i = 0; i != g[top].size(); ++i){
      if(d[g[top][i].nod] <= d[top] + g[top][i].cost)
        continue;
      d[g[top][i].nod] = d[top] + g[top][i].cost;
      if(p[g[top][i].nod] == 0){
        p[g[top][i].nod] = ++num;
        h[num] = g[top][i].nod;
      }
      upheap(p[g[top][i].nod]);
    }
  }
}

void print(){
  int i;
  for(i = 2; i <= n; ++i)
    printf("%d ", d[i]);
  printf("\n");
}

int main(){
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  
  scan();
  
  dijkstra();
  
  print();
  
  return 0;
}