2243. Find the Girl @ Timus Online Judge

2243. Find the Girl

Time limit: 2.0 second
Memory limit: 256 MB

“Once I met a girl in a bar. We had a great conversation, I liked her. She gave me her phone number. The next day I wanted to ask her out, but the number turned out to be invalid. Surely she made a mistake, so I wrote a program that tries all numbers with one mistake and checks whether such a number exists. It found a few, but when I checked social networks for these numbers, none of them was hers. No problem, surely she made two mistakes in the number! The new program found even more numbers, I checked social networks for each of them, and, believe it or not, among the last ones I found her account! I looked through her whole family and all her friends, and finally I called the number. She answered that she had no idea who this was...” — a legendary competitive programmer from the Urals.

At the university there are N rooms. Ignat found out that a girl who once gave him a fake phone number very recently walked through these rooms. He definitely needs to find her in order to clarify the incorrect number.

Ignat interviewed M classmates. The i-th one said that he saw the girl leaving room u_i and going straight to room v_i, possibly more than once. The testimonies turned out to be contradictory, so Ignat assigned each classmate a trust value p_i. It means that if at some moment the girl was in room u_i, then with probability p_i she went to room v_i; at the same time, the girl could have been in the same room any number of times, and from some rooms she might not have left at all, that is, she stopped.

Note that Ignat has no information about other moves between rooms, so he assumes that the girl did not make them.

Ignat also noticed that each room belongs to at most one sequence of cyclic testimonies (that is, testimonies according to which the girl walked around in a circle).

Ignat does not know in which room the girl started; every starting room is equally likely. At the same time, the girl could make any number of moves. For each room, determine the probability that the girl stopped exactly in it.

Input

The first line contains two integers N and M — the number of rooms in the university and the number of testimonies from classmates (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 2 · 10⁵).

The next M lines describe the testimonies with three integers u_i, v_i, and p_i — the girl leaves room u_i and goes to room v_i with probability p_i / 10⁵ (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 0 ≤ p_i ≤ 10⁵).

It is guaranteed that each ordered pair (u_i; v_i) appears at most once. It is also guaranteed that for every room, the sum of probabilities of leaving it does not exceed 1.

Output

For each room, output the probability that the girl stopped in it. The probabilities must be output modulo 10⁹ + 7, that is, if the probability was equal to p / q, then you need to output such an x that 0 ≤ x ≤ 10⁹ + 6 and q · x ≡ p (mod 10⁹ + 7).

Sample

input	output
6 8 1 6 25000 6 3 10000 3 1 60000 6 4 40000 3 4 0 4 5 20000 5 2 100000 2 5 100000	236040611 0 543147212 545177669 0 956006775

Notes

In the example, the probabilities are 83/394, 0, 15/197, 70/591, 0, 206/985.

Problem Author: Vadim Barinov
Problem Source: The 2026 ICPC UrFU Qualification