/*
  Copyright 2011 Marek "p2004a" Rusinowski
  Bellman–Ford algorithm
*/
#include <cstdio>
#include <algorithm>
#include <vector>
 
#define MAXN 1000000
#define INF 0x7FFFFFF0
 
std::vector<std::pair<int, int> > edges[MAXN];
int d[MAXN], n, m;
 
bool bellman_ford(int v) {
  std::fill(d, d + n, INF);
  d[v] = 0;
  bool con;
  for (int j = 0; j < n; ++j) {
    con = false;
    for (int v = 0; v < n; ++v) {
      for (unsigned i = 0; i < edges[v].size(); ++i) {
        if (d[v] + edges[v][i].second < d[edges[v][i].first]) {
          d[edges[v][i].first] = d[v] + edges[v][i].second;
          con = true;
        }
      }
    }
    if (!con) {
      return true;
    }
  }
  return false;
}
 
int main() {
  int a, b, c;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    edges[--a].push_back(std::make_pair(--b, c));
  }
  if (!bellman_ford(0)) {
    printf("false\n");
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    printf("%d ", d[i]);
  }
  printf("\n");
  return 0;
}
 

LyoKICBDb3B5cmlnaHQgMjAxMSBNYXJlayAicDIwMDRhIiBSdXNpbm93c2tpCiAgQmVsbG1hbuKAk0ZvcmQgYWxnb3JpdGhtCiovCiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CgojZGVmaW5lIE1BWE4gMTAwMDAwMAojZGVmaW5lIElORiAweDdGRkZGRkYwCgpzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+ID4gZWRnZXNbTUFYTl07CmludCBkW01BWE5dLCBuLCBtOwoKYm9vbCBiZWxsbWFuX2ZvcmQoaW50IHYpIHsKICBzdGQ6OmZpbGwoZCwgZCArIG4sIElORik7CiAgZFt2XSA9IDA7CiAgYm9vbCBjb247CiAgZm9yIChpbnQgaiA9IDA7IGogPCBuOyArK2opIHsKICAgIGNvbiA9IGZhbHNlOwogICAgZm9yIChpbnQgdiA9IDA7IHYgPCBuOyArK3YpIHsKICAgICAgZm9yICh1bnNpZ25lZCBpID0gMDsgaSA8IGVkZ2VzW3ZdLnNpemUoKTsgKytpKSB7CiAgICAgICAgaWYgKGRbdl0gKyBlZGdlc1t2XVtpXS5zZWNvbmQgPCBkW2VkZ2VzW3ZdW2ldLmZpcnN0XSkgewogICAgICAgICAgZFtlZGdlc1t2XVtpXS5maXJzdF0gPSBkW3ZdICsgZWRnZXNbdl1baV0uc2Vjb25kOwogICAgICAgICAgY29uID0gdHJ1ZTsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIGlmICghY29uKSB7CiAgICAgIHJldHVybiB0cnVlOwogICAgfQogIH0KICByZXR1cm4gZmFsc2U7Cn0KCmludCBtYWluKCkgewogIGludCBhLCBiLCBjOwogIHNjYW5mKCIlZCAlZCIsICZuLCAmbSk7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyArK2kpIHsKICAgIHNjYW5mKCIlZCAlZCAlZCIsICZhLCAmYiwgJmMpOwogICAgZWRnZXNbLS1hXS5wdXNoX2JhY2soc3RkOjptYWtlX3BhaXIoLS1iLCBjKSk7CiAgfQogIGlmICghYmVsbG1hbl9mb3JkKDApKSB7CiAgICBwcmludGYoImZhbHNlXG4iKTsKICAgIHJldHVybiAwOwogIH0KICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgcHJpbnRmKCIlZCAiLCBkW2ldKTsKICB9CiAgcHJpbnRmKCJcbiIpOwogIHJldHVybiAwOwp9Cg==

NCAzCjEgMiAxCjIgMyAtMQozIDQgMQo=

4 3
1 2 1
2 3 -1
3 4 1