D. Это птица! Нет, это самолет! Нет, это AaParsa!
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Шааззззляндии есть $$$n$$$ городов, пронумерованных от $$$0$$$ до $$$n-1$$$. Гааззззляндией, бессмертным врагом Шааззззляндии, правит AaParsa.

Будучи главой разведывательной службы Гааззззляндии, AaParsa выполняет самую важную шпионскую миссию в истории Гааззззляндии на Шааззззляндии.

AaParsa установил $$$m$$$ транспортных пушек в городах Шааззззляндии. $$$i$$$-я пушка установлена в городе $$$a_i$$$ и изначально направлена на город $$$b_i$$$.

Гарантируется, что в каждом из $$$n$$$ городов есть по крайней мере одна транспортная пушка, и что никакие две пушки из одного города изначально не направлены на один и тот же город (то есть, все пары $$$(a_i, b_i)$$$ попарно различны).

AaParsa использовал очень продвинутую технологию для создания пушек, пушки вращаются каждую секунду. Другими словами, если $$$i$$$-я пушка направлена на город $$$x$$$ в какую-то секунду, то в следующую секунду она будет нацелена на город $$$(x + 1) \mod n$$$.

Транспортные пушки, как следует из их названия, предназначены для транспортировки, в частности, для перевозки людей. Если вы используете $$$i$$$-ю пушку, чтобы запустить себя в направлении города, на который она сейчас нацелена, вы будете находиться в воздухе в течение $$$c_i$$$ секунд, прежде чем достигнете цели.

Если вы все еще не поняли, использование $$$i$$$-й пушки на $$$s$$$-й секунде (что возможно, только если вы в данный момент находитесь в городе $$$a_i$$$) запустит вас в город $$$(b_i + s) \mod n$$$, и вы приземлитесь в нем через $$$c_i$$$ секунд (таким образом, вы окажетесь там в $$$(s + c_i)$$$-ю секунду). Обратите внимание, что пушка, из которой вы изначально стартовали, будет вращаться каждую секунду, но вы, очевидно, не будете менять направление, пока находитесь в воздухе.

В своем грандиозном плане AaParsa хочет использовать пушки для перемещения между городами Шааззляндии, и он может начать перемещения в секунду $$$0$$$. Чтобы использовать их в полной мере, ему нужно знать минимальное количество секунд, необходимое для достижения города $$$u$$$ из города $$$v$$$ с помощью пушек, для каждой пары городов $$$(u, v)$$$.

Обратите внимание, что AaParsa может оставаться в любом городе столько, сколько захочет.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ $$$(2 \le n \le 600 , n \le m \le n^2)$$$ — количество городов и пушек соответственно.

В $$$i$$$-й строке следующих $$$m$$$ строк содержатся три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ $$$( 0 \le a_i , b_i \le n-1 , 1 \le c_i \le 10^9)$$$, обозначающие пушку в городе $$$a_i$$$, которая изначально направлена на $$$b_i$$$ и путешествие c которой занимает $$$c_i$$$ секунд.

Гарантируется, что в каждом из $$$n$$$ городов есть по крайней мере одна транспортная пушка, и что никакие две пушки из одного города изначально не направлены на один и тот же город (то есть, все пары $$$(a_i, b_i)$$$ попарно различны).

Выходные данные

Выведите $$$n$$$ строк, каждая из которых должна содержать $$$n$$$ целых чисел.

$$$j$$$-е целое число в $$$i$$$-й строке должно быть равно минимальному времени, необходимому для достижения города $$$j$$$ из города $$$i$$$.

Примеры
Входные данные
3 4
0 1 1
0 2 3
1 0 1
2 0 1
Выходные данные
0 1 2 
1 0 2 
1 2 0
Входные данные
6 6
0 0 1
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
Выходные данные
0 2 3 3 4 4 
4 0 2 3 3 4 
4 4 0 2 3 3 
3 4 4 0 2 3 
3 3 4 4 0 2 
2 3 3 4 4 0
Входные данные
4 5
0 1 1
1 3 2
2 2 10
3 0 1
0 0 2
Выходные данные
0 1 2 3 
3 0 3 2 
12 13 0 11 
1 2 2 0
Примечание

В первом примере один из возможных путей перехода от $$$0$$$ к $$$2$$$ был бы таким:

  1. Остаться внутри $$$0$$$ и ничего не делать в течение $$$1$$$ секунды.
  2. Использовать первую пушку и приземлиться в $$$2$$$ через $$$1$$$ секунду.
Обратите внимание: мы могли бы использовать вторую пушку в $$$0$$$-ю секунду, но в этом случае нам потребовалось бы $$$3$$$ секунды, чтобы достичь города $$$2$$$.