Codeforces Round 722 (Div. 1) |
---|
Закончено |
В Шааззззляндии есть $$$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$$$ был бы таким:
Название |
---|