#include <cstdio>
#include <queue>
using namespace std;
#define NMAX 50005
#define INFINIT 1000000000

int n, m, d[NMAX];
typedef pair<int, int> ii;
vector<ii>a[NMAX];

void daijstra(int start){
  priority_queue<ii, vector<ii>, greater<ii> >pq;
  pq.push(ii(0, start));
  d[start] = 0;
  int dist, current, child, cost, i;

  while(!pq.empty()){
    dist = pq.top().first;
    current = pq.top().second;
    pq.pop();

    if(d[current] < dist)
      continue;

    for(i=0; i<(int)a[current].size(); i++){
      child = a[current][i].first;
      cost = a[current][i].second;
      if(d[child] > d[current] + cost){
        d[child] = d[current] + cost;
        pq.push(ii(d[child], child));
      }
    }
  }
}

int main(){

  int i, x, y, z, start = 1;
  FILE *fin, *fout;
  fin = fopen("dijkstra.in", "r");
  fout = fopen("dijkstra.out", "w");

  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=m; i++){
    fscanf(fin, "%d%d%d", &x, &y, &z);
    a[x].push_back(ii(y, z));
  }

  for(i=2; i<=n; i++){
    d[i] = INFINIT;
  }

  daijstra(start);

  for(i=2; i<=n; i++){
    if(d[i] == INFINIT){
      fprintf(fout, "0 ");
    }else{
      fprintf(fout, "%d ", d[i]);
    }
  }
  return 0;
}