405726: GYM102056 A Exotic … Ancient City

"Welcome to the ancient city Xi'an!"

Coming down the gangway and coming up the stairs, Rikka feels a strong exoticism among the simplified Chinese characters and clean frameless designs.

It all started with that letter, an invitation to Xi'an for a one-week trip from the author named LCR. The mysterious name refers to a girl who is probably from Xi'an or Yuyang — Rikka got such information after a week of hard work. As the lord of Evil Eye, she has a great interest in this, even stronger than that to the city with a millennium history which used to be the capital of 13 dynasties.

Finally, Rikka reached this less valued city, looking forward to an amazing meeting quixotically.

But LCR never appeared. Bored Rikka noticed a map of Xi'an on the wall of the hall. The roads inherit Tang Chang'an city's mesh layout, just like a chessboard. Rikka has felt its convenience since visiting Kyoto, but she also knows about the problems. Crossings block the traffic and the old roads occupy the space for new efficient designs.

This has reminded the girl about her perfect unique solution. Her traffic system includes a set of teleporter vertices $$$V$$$ and a set of some bidirectional horizon-wormhole edges $$$E$$$ linking them. People can teleport from one terminal to the other in no time. The vertices form an $$$n \times (m+1)$$$ grid, that is, there are $$$n$$$ rows and $$$(m+1)$$$ columns, containing $$$n \cdot (m+1)$$$ vertices in total. Let $$$\langle x, y \rangle~(x, y \in \mathbb{N}, x\in [1, n], y\in [1,{m+1}])$$$ be the vertex at the $$$x$$$-th row of the $$$y$$$-th column. In her initial design, every edge is between two vertices in distinct adjacent columns, and for each pair of adjacent columns, the edges among them are similar. That is, if $$$(\langle x,y \rangle, \langle z,y+1 \rangle) \in E$$$, then for $$$i = 1, 2, \dots, m, (\langle x,i \rangle, \langle z,i+1 \rangle) \in E$$$ holds. Also, people can travel by the edges between any pair of vertices in each two-column subsystem, which means, for $$$i = 1, 2, \dots, m$$$, if we remove all vertices and edges except those in or between the $$$i$$$-th column and the $$$(i + 1)$$$-th column, the remaining vertices are still connected. No two edges connect the same pair of vertices.

Actually, the horizon-wormholes are expensive. Rikka knows each edge has an integer cost level, but the cost levels are fairly low because the energy of horizon-wormholes is too large and chaotic to measure or calculate accurately. The edges connecting the same pair of rows in every column have the same cost. That is, $$$\forall x, y, i, j$$$, $$$w(( \langle x, i \rangle , \langle y, i + 1 \rangle )) = w(( \langle x, j \rangle , \langle y, j + 1 \rangle ))$$$ if $$$( \langle x, i \rangle , \langle y, i + 1 \rangle ), ( \langle x, j \rangle , \langle y, j + 1 \rangle ) \in E$$$ , where $$$w(e)$$$ is the cost of edge $$$e$$$. Now Rikka wants to delete some (maybe zero) edges in order to minimize the total cost which is the sum of costs of all remained edges. The connectivity among all vertices must hold. That is, we can still travel between each pair of vertices, possibly passing any other columns. However, connecting each two-column subsystem or keeping edges between each pair of adjacent columns the same is not necessary.

Also, she may only use a consecutive part of columns of her initial design, so the answer for each fewer $$$m$$$ is needed. Could you help her?

The first line contains three positive integers $$$n, M, e~(1\le n\le 10^5, 1\le M\le 10^5, 1\le e\le 2 \times 10^5)$$$, describing the number of rows, the maximal possible columns and the number of edges in each pair of adjacent columns, respectively. You need to calculate the answer for each subsystem of $$$(m+1)~(1\le m\le M)$$$ columns while the edges between each pair of columns remain.

Each of the following $$$e$$$ lines describes a group of edges, containing three positive integers $$$u, v, w~(1\le u,v\le n, 1\le w\le 30)$$$, meaning that for $$$i = 1, 2, \dots, m$$$ there is an edge $$$(\langle u,i \rangle, \langle v,i+1 \rangle)\in E$$$ with a cost of $$$w$$$. No two edges connect the same pair of vertices, and people can travel between any pair of vertices in the subsystem of each $$$m$$$.

Output $$$M$$$ lines. The $$$m$$$-th line contains a single integer, the minimum total cost for the subsystem of $$$(m + 1)$$$ columns.

4 4 8
3 4 12
1 1 20
1 3 22
4 2 12
4 4 2
2 2 2
1 2 2
1 4 2

62
80
98
116

6 6 15
1 2 1
1 3 1
3 4 1
2 4 1
6 3 2
6 5 2
3 5 2
2 3 2
4 3 2
6 4 2
5 4 2
4 6 2
6 6 2
5 5 3
5 1 3

19
28
37
46
55
64

The subsystems of all possible $$$m~(1 \leq m \leq M)$$$ in sample $$$1$$$ are shown below. The images show one optimal way to delete the roads: the deleted roads are painted blue (as dark grey if the document is printed in black and white), and the others are painted orange (as light grey if the document is printed in black and white).