#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int maxN = 50000;
const int maxM = 250000;
const int infi = 0x3f3f3f3f;
int N, M, d[maxN];

typedef pair<int, int> muchie; /// first = nodul, second = lungimea
priority_queue<muchie> H;
vector<muchie> G[maxN + 1];

void reset() {
  for(register int i = 2; i <= N; ++ i)
    if(d[i] == infi)
      d[i] = 0;
}

void dijkstra() {
  for(register int i = 2; i <= N; ++ i)
    d[i] = infi;

  H.push(make_pair(1, 0));
  while(!H.empty()) {
    int length = H.top().second, nod = H.top().first;
    H.pop();
    for(auto it = G[nod].begin(); it != G[nod].end(); ++ it) {
      if(length + it->second < d[it->first]) {
        d[it->first] = length + it->second;
        H.push(make_pair(it->first, d[it->first]));
      }
    }
  }
  reset();
}


void bellman_ford() {
  bool inCoada[maxN];
  queue<int> C;

  memset(d, infi, sizeof d);
  memset(inCoada, false, sizeof inCoada);

  d[1] = 0;
  C.push(1);
  inCoada[1] = true;

  while(!C.empty()) {
    int x = C.front(); C.pop();
    inCoada[x] = false;

    for(auto it = G[x].begin(); it != G[x].end(); ++ it) {
      if(d[x] + it->second < d[it->first]) {
        d[it->first] = d[x] + it->second;
        if(!inCoada[it->first]) {
          C.push(it->first);
          inCoada[it->first] = true;
        }
      }
    }
  }

  reset();
}

int main() {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  scanf("%d %d", &N, &M);
  for(register int i = 1; i <= M; ++ i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    G[a].push_back(make_pair(b, c));
  }

  bellman_ford();
  for(register int i = 2; i <= N; ++ i)
    printf("%d ", d[i]);
  printf("\n");
  return 0;
}