It's a bird! No, it's a plane! No, it's AaParsa!
Contest: Codeforces Round 722 (Div. 1)
Difficulty rating: 2500
Tags: constructive algorithms, graphs, shortest paths

There are $$$n$$$ cities in Shaazzzland, numbered from $$$0$$$ to $$$n-1$$$. Ghaazzzland, the immortal enemy of Shaazzzland, is ruled by AaParsa.

As the head of the Ghaazzzland's intelligence agency, AaParsa is carrying out the most important spying mission in Ghaazzzland's history on Shaazzzland.

AaParsa has planted $$$m$$$ transport cannons in the cities of Shaazzzland. The $$$i$$$-th cannon is planted in the city $$$a_i$$$ and is initially pointing at city $$$b_i$$$.

It is guaranteed that each of the $$$n$$$ cities has at least one transport cannon planted inside it, and that no two cannons from the same city are initially pointing at the same city (that is, all pairs $$$(a_i, b_i)$$$ are distinct).

AaParsa used very advanced technology to build the cannons, the cannons rotate every second. In other words, if the $$$i$$$-th cannon is pointing towards the city $$$x$$$ at some second, it will target the city $$$(x + 1) \mod n$$$ at the next second.

As their name suggests, transport cannons are for transportation, specifically for human transport. If you use the $$$i$$$-th cannon to launch yourself towards the city that it's currently pointing at, you'll be airborne for $$$c_i$$$ seconds before reaching your target destination.

If you still don't get it, using the $$$i$$$-th cannon at the $$$s$$$-th second (using which is only possible if you are currently in the city $$$a_i$$$) will shoot you to the city $$$(b_i + s) \mod n$$$ and you'll land in there after $$$c_i$$$ seconds (so you'll be there in the $$$(s + c_i)$$$-th second). Also note the cannon that you initially launched from will rotate every second but you obviously won't change direction while you are airborne.

AaParsa wants to use the cannons for travelling between Shaazzzland's cities in his grand plan, and he can start travelling at second $$$0$$$. For him to fully utilize them, he needs to know the minimum number of seconds required to reach city $$$u$$$ from city $$$v$$$ using the cannons for every pair of cities $$$(u, v)$$$.

Note that AaParsa can stay in a city for as long as he wants.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(2 \le n \le 600 , n \le m \le n^2)$$$ — the number of cities and cannons correspondingly.

The $$$i$$$-th line of the following $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ $$$( 0 \le a_i , b_i \le n-1 , 1 \le c_i \le 10^9)$$$, denoting the cannon in the city $$$a_i$$$, which is initially pointing to $$$b_i$$$ and travelling by which takes $$$c_i$$$ seconds.

It is guaranteed that each of the $$$n$$$ cities has at least one transport cannon planted inside it, and that no two cannons from the same city are initially pointing at the same city (that is, all pairs $$$(a_i, b_i)$$$ are distinct).

Output format:
Print $$$n$$$ lines, each line should contain $$$n$$$ integers.

The $$$j$$$-th integer in the $$$i$$$-th line should be equal to the minimum time required to reach city $$$j$$$ from city $$$i$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first example one possible path for going from $$$0$$$ to $$$2$$$ would be:

1. Stay inside $$$0$$$ and do nothing for $$$1$$$ second.
2. Use the first cannon and land at $$$2$$$ after $$$1$$$ second.

Example input:
3 4
0 1 1
0 2 3
1 0 1
2 0 1

Example output:
0 1 2 
1 0 2 
1 2 0

Example input:
6 6
0 0 1
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1

Example output:
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

Editorial:
Suppose we did normal dijkstra, the only case that might be missed is when we wait in a vertex for some time.
To handle the 'waiting' concept, we can add $$$n$$$ fake edges, $$$i$$$-th of which is from the $$$i$$$-th vertex to the $$$(i+1 \mod n)$$$ -th vertex with weight equal to one.
Note that unlike the cannons, fake edges do not rotate.
It can be proved that doing dijkstra in the new graph is sufficient if we guarantee that the first used edge is not fake.
We can map waiting for $$$x$$$ seconds and then using an edge to go to $$$u$$$ from $$$v$$$ to using a cannon and then using $$$x$$$ fake edges to go to $$$u$$$ from $$$v$$$.
Also due to the strict time limit you should use the $$$\mathcal{O}(n^2)$$$ variant of dijkstra.
complexity: $$$\mathcal{O}(n^3)$$$