所有的地圖都通往「唯一」（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 的出現，導致自用車使用者突然增加而使道路崩潰，因此指示現代汽車集團計算「道路負擔」這一數值。
幸運的是，基帕在擔任總統前深入研究過數學與工程學，因此他嚴格定義了道路負擔，讓實務人員不必為了創造有意義的指標而絞盡腦汁。對於每一條道路，道路負擔定義為：當每天使用該道路的車輛數為 $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$