Mọi bản đồ đều dẫn về 'một và duy nhất' (Sole), bản đồ dẫn đường thế hệ mới của Hyundai AutoEver 'SoleMap'

Khi lái xe trên một con đường lạ, chắc hẳn ai cũng từng có trải nghiệm khó khăn khi rẽ nhầm ngã ba hoặc đi sai làn đường. Ngay cả khi có hệ thống dẫn đường, việc đối chiếu màn hình dẫn đường với thực tế đường đi trên những cung đường mới thường không dễ dàng. SoleMap là bản đồ dẫn đường thế hệ mới mà Hyundai AutoEver đang xây dựng để giải quyết những bất tiện này cho người lái xe. SoleMap là cái tên nhấn mạnh ý nghĩa của sự tích hợp, kết hợp giữa tính từ Sole (có nghĩa là 'duy nhất') và bản đồ (Map). SoleMap đặt mục tiêu được tích hợp vào các hệ thống dẫn đường thực tế trong năm 2024.

Cấu trúc đường bộ của Vương quốc Thẳng (Straight Land) có thể được coi là $N$ thành phố nằm trên một đường thẳng, trong đó với mọi $1 \leq i \leq (N-1)$, thành phố thứ $i$ và thành phố thứ $(i+1)$ được kết nối trực tiếp bởi một con đường hai chiều có $w_{i}$ làn xe. Tại Vương quốc Thẳng này, mỗi ngày có $x_{j}$ chiếc xe di chuyển từ thành phố $u_{j}$ đến thành phố $v_{j}$. Do đó, tổng cộng có $\sum_{j} x_{j}$ chiếc xe di chuyển mỗi ngày. Mặc dù lộ trình di chuyển trong Vương quốc Thẳng là duy nhất, nhưng tùy thuộc vào việc sử dụng làn đường nào mà xe có thể di chuyển nhanh hơn hoặc chậm hơn do tắc nghẽn. Vì vậy, các hệ thống dẫn đường hiện có chỉ tìm lộ trình mà không phân biệt làn đường đã không mang lại nhiều hiệu quả.

Tổng thống Kipa của Vương quốc Thẳng đã thí điểm áp dụng SoleMap, một hệ thống khác biệt rõ rệt so với các hệ thống dẫn đường cũ. Tin tức về việc hệ thống dẫn đường này chỉ dẫn lộ trình nhanh nhất đến từng làn xe đã lan truyền nhanh chóng, và cuối cùng, tất cả các hệ thống dẫn đường tại Vương quốc Thẳng đều trở thành SoleMap. Lo ngại rằng SoleMap có thể khiến lượng người sử dụng xe cá nhân tăng đột biến dẫn đến hư hỏng đường sá, Kipa đã chỉ thị cho Hyundai AutoEver tính toán một giá trị gọi là 'gánh nặng đường bộ'.

May mắn thay, vì Kipa đã nghiên cứu sâu về toán học và kỹ thuật trước khi trở thành tổng thống, ông đã định nghĩa nghiêm ngặt gánh nặng đường bộ để các nhân viên thực thi không phải đau đầu tạo ra các chỉ số có ý nghĩa. Đối với mỗi con đường, gánh nặng đường bộ là giá trị nhỏ nhất của tổng bình phương số lượng xe trên mỗi làn đường, khi $c$ chiếc xe sử dụng con đường đó mỗi ngày được phân bổ hợp lý vào $w$ làn xe.

Ví dụ, đối với một con đường có $c = 4$ và $w = 3$, các làn xe có thể phân bổ số lượng xe như sau:

• Nếu tất cả $4$ chiếc xe đi trên cùng một làn: $4^{2} + 0^{2} + 0^{2} = 16$
• Nếu $3$ chiếc xe đi trên một làn và $1$ chiếc xe đi trên một làn khác: $3^{2} + 1^{2} + 0^{2} = 10$
• Nếu $2$ chiếc xe đi trên một làn và $2$ chiếc xe đi trên một làn khác: $2^{2} + 2^{2} + 0^{2} = 8$
• Nếu $2$ chiếc xe đi trên một làn, $1$ chiếc xe đi trên một làn khác và $1$ chiếc xe đi trên làn còn lại: $2^{2} + 1^{2} + 1^{2} = 6$

Giá trị nhỏ nhất trong số này là $6$ chính là gánh nặng đường bộ.

Là một lập trình viên của SoleMap, hãy nắm bắt cơ hội thăng tiến bằng cách tính toán gánh nặng đường bộ cho từng con đường dựa trên tình hình giao thông của Vương quốc Thẳng!

Dữ liệu vào

Dòng đầu tiên chứa số lượng thành phố $N$ và số lượng thông tin xe cộ $M$ của Vương quốc Thẳng, cách nhau bởi dấu cách. ($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)

Dòng thứ hai chứa $(N-1)$ số nguyên $w_{1}, w_{2}, \cdots, w_{N-1}$ cách nhau bởi dấu cách. ($1 \leq w_{i} \leq 10^{9}$) Điều này có nghĩa là với mỗi $1 \leq i \leq (N-1)$, con đường nối thành phố thứ $i$ và thành phố thứ $(i+1)$ có $w_{i}$ làn xe.

$M$ dòng tiếp theo chứa thông tin về tình hình giao thông của Vương quốc Thẳng. Với mỗi $1 \leq j \leq M$, dòng thứ $(j+2)$ chứa $u_{j}, v_{j}, x_{j}$ cách nhau bởi dấu cách. ($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$) Điều này có nghĩa là mỗi ngày có $x_{j}$ chiếc xe di chuyển từ thành phố $u_{j}$ đến thành phố $v_{j}$.

Tổng của tất cả $x_{j}$ được cho không vượt quá $10^{9}$.

Dữ liệu ra

In ra $(N-1)$ dòng.

Với mỗi $1 \leq i \leq (N-1)$, dòng thứ $i$ in ra gánh nặng đường bộ của con đường nối thành phố thứ $i$ và thành phố thứ $(i+1)$.

Ví dụ

Dữ liệu vào 1

4 2
1 3 4
1 3 3
2 4 1

Dữ liệu ra 1

9
6
1

Ghi chú

Số lượng xe sử dụng mỗi con đường mỗi ngày có thể được tính như sau:

• Con đường nối thành phố $1$ và $2$: $3 + 0 = 3$ chiếc
• Con đường nối thành phố $2$ và $3$: $3 + 1 = 4$ chiếc
• Con đường nối thành phố $3$ và $4$: $0 + 1 = 1$ chiếc

Gánh nặng đường bộ của mỗi con đường có thể được tính như sau:

• Gánh nặng đường bộ của con đường nối thành phố $1$ và $2$: Vì chỉ có một làn xe nên $3^{2} = 9$
• Gánh nặng đường bộ của con đường nối thành phố $2$ và $3$: Như đã giải thích ở trên, là $6$
• Gánh nặng đường bộ của con đường nối thành phố $3$ và $4$: Vì chỉ có một chiếc xe, dù chạy ở làn nào thì cũng là $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$