所有地图都通向“唯一”（Sole），现代汽车集团（Hyundai AutoEver）的下一代导航地图“SoleMap”。
在驾驶前往陌生目的地时，每个人都有过因为走错岔路口或选错车道而陷入困境的经历。即使有导航，初次前往的地方也很难将导航画面与实际道路在脑海中直接对应。SoleMap 是现代汽车集团为了解决这些驾驶员的不便而正在构建的下一代导航地图。SoleMap 是由意为“唯一的”形容词 Sole 和地图（Map）组合而成的名称，强调了整合的意义。SoleMap 的目标是在 2024 年内搭载于实际导航系统中。
直线国的道路结构可以看作有 $N$ 个城市排成一条直线，对于所有 $1 \leq i \leq (N-1)$，第 $i$ 号城市和第 $(i+1)$ 号城市之间由一条双向 $w_{i}$ 车道的道路直接相连。在这样的直线国中，每天有 $x_{j}$ 辆车从 $u_{j}$ 号城市移动到 $v_{j}$ 号城市。因此，直线国每天共有 $\sum_{j} x_{j}$ 辆车在移动。虽然直线国的移动路径是唯一的，但根据所使用的车道不同，可能会更快到达，也可能因为交通拥堵而更慢。因此，不区分车道、只提供路径的现有导航系统并没有太大帮助。
直线国总统 Kipa 试行引入了与现有导航截然不同的 SoleMap。随后，关于导航能精确告知各车道最快路径的消息传开了，最终直线国的所有导航都变成了 SoleMap。担心因为 SoleMap 导致私家车用户激增而造成道路损毁的 Kipa，指示现代汽车集团计算一个名为“道路负担”的数值。
幸运的是，Kipa 在担任总统前深入学习过数学和工程学，因此他严格定义了道路负担，使得工作人员不必为了创造有意义的指标而绞尽脑汁。对于每条道路，道路负担定义为：当每天使用该道路的车辆总数为 $c$ 时，将 $c$ 辆车合理分配到 $w$ 个车道上，使得各车道通过车辆数的平方和达到最小。
例如，对于某条道路，若 $c = 4$，$w = 3$，车道分配方式如下：
- 所有 $4$ 辆车都在同一车道行驶：$4^{2} + 0^{2} + 0^{2} = 16$
- 一车道有 $3$ 辆车，另一车道有 $1$ 辆车：$3^{2} + 1^{2} + 0^{2} = 10$
- 一车道有 $2$ 辆车，另一车道有 $2$ 辆车：$2^{2} + 2^{2} + 0^{2} = 8$
- 一车道有 $2$ 辆车，一车道有 $1$ 辆车，另一车道有 $1$ 辆车：$2^{2} + 1^{2} + 1^{2} = 6$
其中的最小值 $6$ 即为该道路的道路负担。
作为 SoleMap 的程序员，请根据给定的直线国交通状况，计算每条道路的道路负担，争取晋升的机会吧！
输入
第一行给出直线国的城市数量 $N$ 和表示移动车辆信息的整数 $M$，中间用空格隔开。($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)
第二行给出 $(N-1)$ 个整数 $w_{1}, w_{2}, \cdots, w_{N-1}$，中间用空格隔开。($1 \leq w_{i} \leq 10^{9}$) 这表示对于每个 $1 \leq i \leq (N-1)$，连接第 $i$ 号城市和第 $(i+1)$ 号城市的道路有 $w_{i}$ 个车道。
接下来的 $M$ 行给出直线国的交通状况信息。对于每个 $1 \leq j \leq M$，第 $(j+2)$ 行给出 $u_{j}, v_{j}, x_{j}$，中间用空格隔开。($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$) 这表示每天有 $x_{j}$ 辆车从 $u_{j}$ 号城市移动到 $v_{j}$ 号城市。
所有给定的 $x_{j}$ 之和不超过 $10^{9}$。
输出
输出 $(N-1)$ 行。
对于每个 $1 \leq i \leq (N-1)$，第 $i$ 行输出连接第 $i$ 号城市和第 $(i+1)$ 号城市的道路的道路负担。
样例
输入 1
4 2 1 3 4 1 3 3 2 4 1
输出 1
9 6 1
说明
可以按如下方式计算每天使用各道路的车辆数：
- 连接 $1$ 号城市和 $2$ 号城市的道路：$3 + 0 = 3$ 辆
- 连接 $2$ 号城市和 $3$ 号城市的道路：$3 + 1 = 4$ 辆
- 连接 $3$ 号城市和 $4$ 号城市的道路：$0 + 1 = 1$ 辆
可以按如下方式计算各道路的道路负担：
- 连接 $1$ 号城市和 $2$ 号城市的道路的道路负担：因为只有一条车道，所以 $3^{2} = 9$
- 连接 $2$ 号城市和 $3$ 号城市的道路的道路负担：如前所述，为 $6$
- 连接 $3$ 号城市和 $4$ 号城市的道路的道路负担：因为只有一辆车，无论在哪条车道行驶，结果均为 $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$