В университете есть N кабинетов. Игнат узнал, что одна девушка, которая когда-то давно дала ему фейковый номер телефона, совсем недавно прошлась по этим кабинетам. Её точно нужно найти, чтобы уточнить неправильный номер.

Игнат опросил M одногруппников, i-й сказал, что видел, как девушка выходила из u_i-го кабинета и шла прямиком в v_i-й, возможно, и не один раз. Показания получились противоречивыми, поэтому каждому одногруппнику Игнат присвоил значение доверия p_i. Оно означает, что если девушка в какой-либо момент оказалась в кабинете u_i, то с вероятностью p_i она пошла в кабинет v_i, при этом девушка могла оказаться в одном и том же кабинете любое количество раз, а из некоторых она могла и не выходить, то есть она остановилась.

Заметьте, что Игнат не имеет информации про остальные переходы между кабинетами, поэтому считает, что девушка так не ходила.

Также Игнат заметил, что никакой кабинет не мог оказаться больше чем в одной последовательности циклических показаний (таких показаний, что согласно им девушка шла по кругу).

Игнат не знает, в каком кабинете начинала девушка, каждый начальный кабинет одинаково возможен. При этом девушка могла сделать сколько угодно переходов. Для каждого кабинета определите вероятность того, что девушка остановилась именно в нём.

В первой строке даются два целых числа N и M — количество кабинетов в университете и количество показаний одногруппников (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 2 · 10⁵).

В следующих M строках описываются показания тремя целыми числами u_i, v_i и p_i — девушка из кабинета u_i выходит в кабинет v_i с вероятностью p_i / 10⁵ (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 0 ≤ p_i ≤ 10⁵).

Гарантируется, что каждая упорядоченная пара (u_i; v_i) встречается не больше одного раза. Гарантируется, что для любого кабинета сумма вероятностей выхода из него не больше 1.

Для каждого кабинета выведите вероятность того, что девушка в нём остановилась. Вероятности надо выводить по модулю 10⁹ + 7, то есть, если вероятность была равна p / q, то необходимо вывести такое x, что 0 ≤ x ≤ 10⁹ + 6 и q · x ≡ p (mod 10⁹ + 7).

В примере вероятности равны 83/394, 0, 15/197, 70/591, 0, 206/985.