Problem: You are given a directed acyclic graph (a directed graph that does not contain cycles) of n vertices and m arcs. The i-th arc leads from the vertex x_i to the vertex y_i and has the weight w_i.

Your task is to select an integer a_v for each vertex v, and then write a number b_i on each arcs i such that b_i = a_{x_i} - a_{y_i}. You must select the numbers so that:

  * all b_i are positive; 
  * the value of the expression ∑ _{i = 1}^{m} w_i b_i is the lowest possible. 



It can be shown that for any directed acyclic graph with non-negative w_i, such a way to choose numbers exists.

Input

The first line contains two integers n and m (2 ≤ n ≤ 18; 0 ≤ m ≤ (n(n - 1))/(2)).

Then m lines follow, the i-th of them contains three integers x_i, y_i and w_i (1 ≤ x_i, y_i ≤ n, 1 ≤ w_i ≤ 10^5, x_i ≠ y_i) — the description of the i-th arc.

It is guaranteed that the lines describe m arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.

Output

Print n integers a_1, a_2, ..., a_n (0 ≤ a_v ≤ 10^9), which must be written on the vertices so that all b_i are positive, and the value of the expression ∑ _{i = 1}^{m} w_i b_i is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints 0 ≤ a_v ≤ 10^9.

Examples

Input


3 2
2 1 4
1 3 2


Output


1 2 0


Input


5 4
1 2 1
2 3 1
1 3 6
4 5 8


Output


43 42 41 1337 1336


Input


5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10


Output


4 3 2 1 2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
long long chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
long long chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
long long dcmp(T a, T b) {
  return a > b;
}
template <long long *a>
long long cmp_a(long long first, long long second) {
  return a[first] < a[second];
}
template <class T>
bool sort2(T &a, T &b) {
  return a > b ? swap(a, b), 1 : 0;
}
struct __INIT__ {
  __INIT__() {
    fill((unsigned char *)&inf, (unsigned char *)&inf + sizeof(inf), 0x3f);
  }
} __INIT___;
namespace io {
const long long SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
long long f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
long long id[19][19];
pair<long long, long long> e[405];
long long s[19];
namespace flow {
long long to[1000005], lst[1000005], beg[100005], w[1000005],
    e = 1, cur[100005], q[100005], dis[1000005];
long long n, s, t;
void add(long long u, long long v, long long c) {
  to[++e] = v;
  lst[e] = beg[u];
  beg[u] = e;
  w[e] = c;
  to[++e] = u;
  lst[e] = beg[v];
  beg[v] = e;
  w[e] = 0;
}
bool bfs() {
  for (long long i = 1; i <= n; ++i) {
    cur[i] = beg[i];
    dis[i] = n + 1;
  }
  dis[s] = 0;
  long long *l = q, *r = q;
  *(l = r = q) = s;
  while (l <= r) {
    for (long long i = beg[*l]; i; i = lst[i])
      if (w[i] && chkmin(dis[to[i]], dis[*l] + 1)) *(++r) = to[i];
    ++l;
  }
  return dis[t] < n;
}
long long dfs(long long s, long long t, long long fl) {
  if (s == t) return fl;
  for (long long &i = cur[s]; i; i = lst[i])
    if (w[i] && dis[s] + 1 == dis[to[i]]) {
      long long v = dfs(to[i], t, mmin(fl, w[i]));
      if (v) {
        w[i] -= v;
        w[i ^ 1] += v;
        return v;
      }
    }
  return 0;
}
long long calc() {
  long long flow;
  long long ans = 0;
  while (bfs()) {
    while ((flow = dfs(s, t, 0x7fffffff))) ans += flow;
  }
  return ans;
}
}  // namespace flow
signed main() {
  long long n, m, first, second, w, c = 2;
  read(n, m);
  for (long long i = 1; i <= n; ++i) {
    id[i][0] = 1;
    for (long long j = 1; j < n; ++j) id[i][j] = ++c;
    id[i][n] = 2;
  }
  flow::n = c;
  flow::s = 1;
  flow::t = 2;
  for (long long i = 1; i <= m; ++i) {
    read(first, second, w);
    for (long long j = 0; j < n; ++j)
      flow::add(id[second][j], id[first][j + 1], inf);
    e[i] = {first, second};
    s[first] += w;
    s[second] -= w;
  }
  long long ans = 0;
  for (long long i = 1; i <= n; ++i) {
    if (s[i] == 0) continue;
    if (s[i] > 0) {
      for (long long j = 1; j <= n; ++j)
        flow::add(id[i][j - 1], id[i][j], j * s[i]);
    } else {
      ans += n * s[i];
      for (long long j = 1; j <= n; ++j) {
        flow::add(id[i][j - 1], id[i][j], (j - n) * s[i]);
      }
    }
  }
  flow::calc();
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 1; j <= n; ++j)
      if (flow::dis[id[i][j - 1]] <= c && flow::dis[id[i][j]] > c) {
        write(j, i == n ? '\n' : ' ');
        break;
      }
  }
  return 0;
}