“欢迎来到古城西安！”

走下舷梯，拾级而上，Rikka 在简体汉字和简洁的无框设计中感受到了浓郁的异域风情。

这一切都始于那封信，一封来自名为 LCR 的作者的邀请函，邀请她去西安进行为期一周的旅行。这个神秘的名字指向了一位可能来自西安或榆阳的女孩——Rikka 在经过一周的努力后得到了这一信息。作为“邪王真眼”的持有者，她对此产生了极大的兴趣，甚至超过了对这座曾经作为 13 个王朝首都、拥有千年历史的城市的兴趣。

最终，Rikka 来到了这座被低估的城市，满怀憧憬地期待着一场奇妙的邂逅。

但 LCR 始终没有出现。百无聊赖的 Rikka 注意到了大厅墙上的一张西安地图。这里的道路继承了唐长安城的网格布局，就像棋盘一样。Rikka 自从访问京都以来就感受到了这种布局的便利，但她也知道其中的问题。十字路口阻碍了交通，而老旧的道路占据了空间，影响了新的高效设计。

这让女孩想到了她那完美的独特解决方案。她的交通系统包括一组传送顶点 $V$ 和一组连接它们的双向地平线虫洞边 $E$。人们可以在瞬间从一个终端传送到另一个终端。顶点构成了一个 $n \times (m + 1)$ 的网格，即共有 $n$ 行和 $(m + 1)$ 列，总计包含 $n \times (m + 1)$ 个顶点。令 $\langle x, y \rangle$ ($x, y \in \mathbb{N}, x \in [1, n], y \in [1, m + 1]$) 表示第 $y$ 列第 $x$ 行的顶点。在她的初始设计中，每条边都连接两个不同相邻列中的顶点，并且对于每一对相邻的列，它们之间的边都是相似的。也就是说，如果 $(\langle x, i \rangle, \langle z, i + 1 \rangle) \in E$，那么对于 $i = 1, 2, \dots, m$，$(\langle x, i \rangle, \langle z, i + 1 \rangle) \in E$ 成立。此外，人们可以通过每两个相邻列子系统中的边在任意一对顶点之间穿行，这意味着对于 $i = 1, 2, \dots, m$，如果我们移除除第 $i$ 列和第 $(i + 1)$ 列中或之间的所有顶点和边，剩余的顶点仍然是连通的。没有两条边连接同一对顶点。

实际上，地平线虫洞非常昂贵。Rikka 知道每条边都有一个整数成本等级，但由于地平线虫洞的能量太大且难以精确测量或计算，成本等级相当低。在每一列中，连接相同行对的边具有相同的成本。也就是说，$\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)$，如果 $(\langle x, i \rangle, \langle y, i + 1 \rangle), (\langle x, j \rangle, \langle y, j + 1 \rangle) \in E$，其中 $w(e)$ 是边 $e$ 的成本。现在 Rikka 想要删除一些（可能是零条）边，以最小化总成本，即所有剩余边的成本之和。所有顶点之间的连通性必须保持。也就是说，我们仍然可以在每一对顶点之间穿行，可能经过任何其他列。然而，连接每个两列子系统或保持每对相邻列之间的边相同是不必要的。

此外，她可能只使用初始设计中连续的一部分列，因此需要针对每个较小的 $m$ 的答案。你能帮帮她吗？

输入格式

第一行包含三个正整数 $n, M, e$ ($1 \le n \le 10^5, 1 \le M \le 10^5, 1 \le e \le 2 \times 10^5$)，分别描述行数、最大可能的列数以及每对相邻列之间的边数。你需要计算每个 $(m + 1)$ 列子系统（$1 \le m \le M$）的答案，同时保持每对相邻列之间的边。

接下来的 $e$ 行，每行描述一组边，包含三个正整数 $u, v, w$ ($1 \le u, v \le n, 1 \le w \le 30$)，意味着对于 $i = 1, 2, \dots, m$，存在一条边 $(\langle u, i \rangle, \langle v, i + 1 \rangle) \in E$，其成本为 $w$。没有两条边连接同一对顶点，且人们可以在每个 $m$ 的子系统中在任意一对顶点之间穿行。

输出格式

输出 $M$ 行。第 $m$ 行包含一个整数，表示 $(m + 1)$ 列子系统的最小总成本。

样例

样例输入 1

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

样例输出 1

62
80
98
116

样例输入 2

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

样例输出 2

19
28
37
46
55
64

说明

样例 1 中所有可能的 $m$ ($1 \le m \le M$) 的子系统如下图所示。图片展示了一种删除道路的最优方法：被删除的道路被涂成蓝色（如果文档是黑白打印的，则为深灰色），其余道路被涂成橙色（如果文档是黑白打印的，则为浅灰色）。