#include <cstdio>
#include <vector>
#include <set>

using namespace std;

__attribute__((always_inline)) void read(int &num) {
  static char inBuffer[0x30D40];

  static unsigned int p = 0x30D3F;
  num = 0x0;

  while(inBuffer[p] < 0x30 | inBuffer[p] > 0x39) {
    ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
  }

  while(inBuffer[p] > 0x2F & inBuffer[p] < 0x3A) {
    num = num * 0xA + inBuffer[p] - 0x30;

    ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
  }
}

char outBuffer[0x61A80];
unsigned int p;

__attribute__((always_inline)) void write(unsigned int x) {
  unsigned int digits = x > 0x3B9AC9FF ? 0xA :
                        x > 0x5F5E0FF  ? 0x9 :
                        x > 0x98967F   ? 0x8 :
                        x > 0xF423F    ? 0x7 :
                        x > 0x1869F    ? 0x6 :
                        x > 0x270F     ? 0x5 :
                        x > 0x3E7      ? 0x4 :
                        x > 0x63       ? 0x3 :
                        x > 0x9        ? 0x2 : 0x1;

  for(unsigned int i = ~ -digits; ~i; --i) {
    outBuffer[p + i] = x % 0xA + 0x30;

    x = x / 0xA;
  }

  p = p + digits;
  outBuffer[p++] = 0x20;
}

const int N = 50000 + 5;
int n, m;
struct road {
  int nod;
  int dist;
};
vector<road>v[N];

bool operator<(road a, road b) {
  if(a.dist == b.dist)
    return a.nod < b.nod;
  return a.dist < b.dist;
}

int d[N];

struct info {
  int nod;
};

bool operator<(info a, info b) {
  if(d[a.nod] == d[b.nod]) {
    return a.nod < b.nod;
  }
  return d[a.nod] < d[b.nod];
}

set<info>tsb;

int main() {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  read(n);
  read(m);
  while(m--) {
    int a, b, d;
    read(a);
    read(b);
    read(d);
    v[a].push_back({b, d});
  }
  d[1] = 0;
  tsb.insert({1});
  for(int i = 2; i <= n; i++) {
    d[i] = (1 << 30);
    tsb.insert({i});
  }
  while(!tsb.empty()) {
    int nod = tsb.begin()->nod;
    int dist = d[nod];
    tsb.erase(tsb.begin());
    for(auto itr : v[nod]) {
      int nou = itr.nod;
      int add = itr.dist;
      if(dist + add < d[nou]) {
        tsb.erase({nou});
        d[nou] = dist + add;
        tsb.insert({nou});
      }
    }
  }
  for(int i = 2; i <= n; i++) {
    if(d[i] == (1 << 30)) {
      write(0);
    } else {
      write(d[i]);
    }
  }
  puts(outBuffer);
  return 0;
}