题目描述

「欢迎来到古城西安」

走下舷梯，六花一眼看到了航站楼的标牌。蓝色背景上纯白的简体汉字令她感到熟悉又陌生，这就是异国情调吗？

她又想起了一周前收到的那封信，为期七天的西安之旅的邀请函。信的署名是 LCR —— 似乎是一位少女，在西安和豫阳市活动。六花在调查之后得到了如此结论。拥有邪王真眼力量的她对这名发信人十分感兴趣。踏上西安土地的她最期待的，并非是与十三朝古都的相遇，而是与她的邂逅。将要发生什么呢？少女拿着折伞，像堂吉诃德那样思索着。

但 LCR 久久没有出现。有些无聊的六花在航站楼中四处探索，最后在一幅西安市地图前驻足。这座城市的格局承袭了自长安起的古制，街道串通南北，横贯东西，犹如一幅棋盘，横亘城中的铁路则成了楚河汉界。这样简洁的交通对于初来乍到的人实在很方便，六花在北京、京都和其它许多远山避水的地方已经体会过这一点了。不过她也知道，老旧的布局不太适应现代经济的运行。

忽然，六花想到自己曾经的设计：那是一个天才般的完美交通方案，系统包含站点集 $V$，它们在境界上联通——相连的站点对构成若干组无向二元关系 $E$（称为边），其中的每一对皆可在瞬间通过传送通道相互抵达。站点的位置组成了一张 $n\times (m+1)$ 的网格，换言之，一共有 $n\times (m+1)$ 个站点排列成 $n$ 行 $m+1$ 列。记第 $x$ 行第 $y$ 列的站点为 $\langle x,y \rangle (x, y\in \mathbb{N}, x\in [1,n], y\in [1,m+1])$。在她最初的设计中，每条边连接的站点都位于相邻的两列，并且每对相邻列之间的连接是相同的——即对于 $i = 1, 2, \dots , m,((\langle x, y\rangle), (\langle z, y+1 \rangle) \in E \rightarrow (\langle x, i\rangle), (\langle z, i+1 \rangle)\in E)$。并且任意两个相邻列组成的子系统都是连通的，换言之，如果我们只保留第 $i,i+1$ 列的点和它们之间的边，人们还是可以通过这些边在这 $2n$ 个点之间任意旅行。不存在两条连接相同站点对的重边。

事实上，这些传送通道是很昂贵的。六花测定了每条边的花费，不过由于这些庞大而混沌的能量难以精确度量，这些数字的有效位数很小。令 $w(e)$ 表示边 $e$ 的花费。不同列之间连接相同行的边的花费是相同的，即 $\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)$。现在六花希望删除这个设计中的一些冗余通道，以在保证所有站点之间互相连通的情况下使得剩下边的花费总和尽可能小。注意，这里只需要所有行、列的站点之间能够直接或间接地通过剩下的通道互相到达即可，并不需要保证相邻两列的站点被它们之间的边连通。

数学挂科的六花希望你帮她算出这个最小总花费。并且由于她可能只用原始设计中的一部分列，你需要对每个更小的 $m$ 都作出回答。

输入格式

第一行三个正整数 $n,M,e$，分别表示站点网格的行数，最大可能的列数以及每相邻两列之间的连接通道数。对于每个整数 $1\le m\le M$，你需要回答连通这样的 $n$ 行 $m+1$ 列站点最小可能的通道费用之和。

接下来 $e$ 行每行三个正整数 $u,v,w$ 表示一组通道：对于任意 $i = 1, 2, \dots , m$，都有 $(\langle u, i \rangle , \langle v, i+1 \rangle) \in E$，且其费用为 $w$。

保证不存在两条连接相同站点对的边，且任意两层站点之间连通。

输出格式

输出 $m$ 行，第 $i$ 行一个整数表示连接 $i+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

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

数据范围与提示

$1\le n\le 10^5, 1\le M\le 10^5, 1\le e\le 2\times 10^5, 1\le u, v\le n, 1\le w\le 30$。