Magic

Time limit: 1 second | Memory limit: 512 megabytes

Magical quokkas keep changing the color of their fur in mysterious ways. At first, every quokka starts with the plain color (color $0$). Then, at each step, the quokka may change into another color. Eventually, the quokka will settle into a final color, which never changes again.

Some colors are transitional: from such a color, the quokka's color might transform into one of several next colors, with fixed probabilities. (a color may change it's color into itself. in other words, there can be i = j transition) The colors are called final if it's one of the possible last color.

You are given the list of transitions between colors: for each observed transition, you know how many times a quokka changed from one color into another.

Formally: - If a line says “$i$ $j$ $c$”, it means that from color $i$, the quokka was seen changing into color $j$ exactly $c$ times. - The probability of going from color $i$ to color $j$ is then proportional to $c$. - If a color does not appear as a source of transitions, then it is a final color.

It is guaranteed that from every color there is some sequence of changes leading to a final color.

Your task is to determine the exact probability that a magical quokka starting in color $0$ will eventually end up in each final color.

The answer should be given as a list of integers: the numerators of the probabilities for each final color. Fractions must be in simplest form.

Constraints and Scoring

For all test cases:

$1 \le N \le 10$
$1 \le M \le N^2$
$0 \le i, j < N$
$1 \le c \le 50$ The test cases are divided into subtasks. Your program must output a correct answer for every test case in a subtask to receive the points for that subtask.
For Subtask $1$ ($20\%$ of points): There is no cyclic transition.
For Subtask $2$ ($80\%$ of points): There are no additional constraints

Input

The first line of input contains two integers $N$ and $M$.
The following $M$ lines contain three integers $i$, $j$, and $c$ indicating that there is a transition between $i$ and $j$ with weight $c$.

Output

Output the probabilities for each final color in increasing order. The probability must be in it's most simple form. If the answer is $1$ or $0$, it should be printed without any denominator.

If you are using C++, since the answer may be large, you should use the __int128 data type.

Sample Input 1

Sample Output 1

1/3 1/3 1/3

Sample Input 2

Sample Output 2

85/162 77/162