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:
It can be shown that for any directed acyclic graph with non-negative $w_i$, such a way to choose numbers exists.
The first line contains two integers $n$ and $m$ ($2 <= n <= 18$; $0 <= m <= frac(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.
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 $\\sum_{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$.
## Input
The first line contains two integers $n$ and $m$ ($2 <= n <= 18$; $0 <= m <= frac(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 $\\sum_{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$.
[samples]
**Definitions**
Let $ G = (V, E) $ be a directed acyclic graph with $ |V| = n $, $ |E| = m $.
For each arc $ e_i \in E $, let $ e_i = (x_i, y_i) $ with weight $ w_i > 0 $.
Let $ a_v \in \mathbb{Z}_{\geq 0} $ be the value assigned to vertex $ v \in V $.
For each arc $ e_i $, define $ b_i = a_{x_i} - a_{y_i} $.
**Constraints**
1. $ 2 \leq n \leq 18 $
2. $ 0 \leq m \leq \frac{n(n-1)}{2} $
3. For all $ i \in \{1, \dots, m\} $: $ 1 \leq x_i, y_i \leq n $, $ x_i \ne y_i $, $ 1 \leq w_i \leq 10^5 $
4. $ G $ is a directed acyclic graph with no multiple arcs between same pair of vertices.
5. $ b_i > 0 $ for all $ i \in \{1, \dots, m\} $ → $ a_{x_i} > a_{y_i} $
6. $ 0 \leq a_v \leq 10^9 $ for all $ v \in V $
**Objective**
Minimize:
$$
\sum_{i=1}^{m} w_i b_i = \sum_{i=1}^{m} w_i (a_{x_i} - a_{y_i})
$$
subject to the above constraints.