#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "dijkstra"
#else
#define ProblemName "fis"
#endif

#define InFile ProblemName ".in"
#define OuFile ProblemName ".out"


const int MAXBUF = 30000000;
char parseBuf[MAXBUF];
char *head;
bool isDigit[255];
char *writeHead;

void parseInit() {
  int a = fread(parseBuf, 1, MAXBUF, stdin);
  parseBuf[a] = 0;
  head = parseBuf;
  memset(isDigit, 0, sizeof isDigit);
  for (int i = '0'; i <= '9'; ++i)
    isDigit[i] = true;
  writeHead = parseBuf + MAXBUF - 1;
}

int nextInt() {
  int ans = 0;
  for (; !isDigit[*head]; ++head);
  for (; isDigit[*head]; ++head)
    ans = ans * 10 + (*head) - '0';
  return ans;
}


void putNumber(int x) {
  if (x == 0)
    *(writeHead--) = '0';
  else {
    while (x) {
      *(writeHead--) = x % 10 + '0';
      x /= 10;
    }
  }
  *(writeHead--) = ' ';
}

const int MAXN = 50010;

vector<pii> G[MAXN];
int dst[MAXN];
int oo;

void Djkstra() {
  priority_queue< pii > Q;
  memset(dst, 0x3F, sizeof dst);
  oo = dst[0];
  Q.push(mp(0, 0));
  dst[0] = 0;
  while (!Q.empty()) {
    int t = Q.top().second;
    int dt = -Q.top().first;
    Q.pop();
    SKIP(dt != dst[t]);
    for (const auto &it : G[t]) {
      int cand = dt + it.second;
      SKIP(cand >= dst[it.first]);
      dst[it.first] = cand;
      Q.push(mp(-cand, it.first));
    }
  }
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  parseInit();
  int N = nextInt(), M = nextInt();
  while (M--) {
    int a = nextInt(), b = nextInt(), c = nextInt();
    --a, --b;
    G[a].push_back(mp(b, c));
  }
  Djkstra();
  for (int i = N - 1; i; --i)
    putNumber((dst[i] == oo) ? 0 : dst[i]);
  *writeHead = 0;
  fwrite(writeHead + 1, 1, parseBuf + MAXBUF - writeHead, stdout);
  return 0;
}