You are given oriented graph with n vertices numbered $1, 2, \dots, n$ and m edges $u_i, v_i$. Oriented edge goes from $u_i$ to $v_i$. Each edge have positive weight $w_i$. You task is to find permutation p of vertices such that total weight of edges oriented from left to right is low. More formally, you task is to minimize $\mathrm{score}(p) = \sum_{i | p(u_i)>p(v_i)} w_i.$

Scoring:
You score for each testcase is
$100 \cdot \frac{\mathrm{score(p)}}{\sum_i w_i}.$

Input Format:
First line contains two space-separated integers $n, m$.
Next m lines contain description of edges in format $u_i, v_i, w_i$.

Output Format:
Output n space-separated integers -- permutation of $1, 2, \dots, n$.

Constraints:
$1 \leqslant n \leqslant 100.$
$1 \leqslant m \leqslant 10,000.$
$1 \leqslant u_i, v_i \leqslant n.$
$u_i \not = v_i$.
$1 \leqslant w_i \leqslant 1,000,000,000.$
Note that graph can contain multiple edges.

Test generation:
Test consist of several groups. Each group generated using the following pseudocode:

def gen(n, m):
    A = 1000000000
    print(n, m)
    for i = 0, 1, ..., m - 1:
        u = random(1, 2, ..., n)
        v = random(1, 2, ..., u - 1, u + 1, ..., n)
        w = random(1, 2, ..., A)
        print(u, v, w)

Group 1:
$n = 100, m = 100$.
This group contains 10 testcases.
Group 2:
$n = 100, m = 500$.
This group contains 10 testcases.
Group 3:
$n = 100, m = 1,000$.
This group contains 10 testcases.
Group 4:
$n = 100, m = 10,000$.
This group contains 10 testcases.