Todos los mapas conducen a uno solo (Sole), el mapa de navegación de próxima generación de Hyundai AutoEver, 'SoleMap'.

Al conducir por una ruta desconocida, todos hemos visto alguna vez a alguien que se confunde al tomar un desvío o un carril equivocado. Incluso con un sistema de navegación, a menudo es difícil relacionar mentalmente la pantalla del navegador con la carretera real en un primer viaje. SoleMap es el mapa de navegación de próxima generación que Hyundai AutoEver está construyendo para resolver las molestias de estos conductores. SoleMap es un nombre que enfatiza el significado de integración, combinando el adjetivo 'Sole' (que significa 'único') con 'Map' (mapa). El objetivo es que SoleMap esté integrado en sistemas de navegación reales dentro de 2024.

La estructura vial del País de la Línea Recta puede pensarse como $N$ ciudades dispuestas en línea recta, donde para todo $1 \leq i \leq (N-1)$, la ciudad $i$ y la ciudad $(i+1)$ están conectadas directamente por una carretera bidireccional de $w_{i}$ carriles. En este País de la Línea Recta, hay $x_{j}$ vehículos que se desplazan diariamente desde la ciudad $u_{j}$ hasta la ciudad $v_{j}$. Por lo tanto, un total de $\sum_{j} x_{j}$ vehículos circulan diariamente por el país. Aunque la ruta de desplazamiento en el País de la Línea Recta es única, dependiendo del carril que se utilice, se puede viajar más rápido o más lento debido a la congestión vehicular. Por ello, los navegadores convencionales, que solo indican la ruta sin distinguir carriles, no han sido de gran ayuda.

Kipa, el presidente del País de la Línea Recta, introdujo de forma piloto SoleMap, que se distingue claramente de los navegadores existentes. La noticia de que el navegador indica eficazmente el camino más rápido a nivel de carril se difundió rápidamente, y finalmente, todos los navegadores del País de la Línea Recta se convirtieron en SoleMap. Preocupado por si el aumento repentino en el uso de vehículos particulares debido a SoleMap pudiera causar el colapso de las carreteras, Kipa ordenó a Hyundai AutoEver calcular un valor llamado 'carga vial'.

Afortunadamente, como Kipa estudió matemáticas e ingeniería a fondo antes de ser presidente, definió rigurosamente la carga vial para que el personal técnico no tuviera que devanarse los sesos creando indicadores significativos. Para cada carretera, la carga vial se define como el valor mínimo de la suma de los cuadrados del número de vehículos que pasan por cada carril, cuando $c$ vehículos que utilizan la carretera diariamente son distribuidos adecuadamente entre $w$ carriles.

Por ejemplo, si para una carretera $c = 4$ y $w = 3$, los carriles pueden distribuir los vehículos de la siguiente manera:

• Si los 4 vehículos circulan por un solo carril: $4^{2} + 0^{2} + 0^{2} = 16$
• Si 3 vehículos circulan por un carril y el vehículo restante por otro: $3^{2} + 1^{2} + 0^{2} = 10$
• Si 2 vehículos circulan por un carril y los otros 2 por otro: $2^{2} + 2^{2} + 0^{2} = 8$
• Si 2 vehículos circulan por un carril, 1 vehículo por otro y el último vehículo por el tercer carril: $2^{2} + 1^{2} + 1^{2} = 6$

El valor mínimo, 6, es la carga vial.

Como programador de SoleMap, ¡intenta calcular la carga vial de cada carretera dada la situación del tráfico en el País de la Línea Recta y busca una oportunidad de ascenso!

Entrada

En la primera línea se proporcionan, separados por un espacio, el número de ciudades $N$ y el número entero $M$ que representa la información de los vehículos que se desplazan por el País de la Línea Recta. ($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)

En la segunda línea se proporcionan $(N-1)$ números enteros $w_{1}, w_{2}, \cdots, w_{N-1}$ separados por espacios. ($1 \leq w_{i} \leq 10^{9}$) Esto significa que, para cada $1 \leq i \leq (N-1)$, la carretera que conecta la ciudad $i$ y la ciudad $(i+1)$ tiene $w_{i}$ carriles.

En las siguientes $M$ líneas se proporciona la información sobre la situación del tráfico en el País de la Línea Recta. Para cada $1 \leq j \leq M$, en la línea $(j+2)$ se proporcionan $u_{j}, v_{j}, x_{j}$ separados por espacios. ($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$) Esto significa que hay $x_{j}$ vehículos que viajan diariamente desde la ciudad $u_{j}$ hasta la ciudad $v_{j}$.

La suma de todos los $x_{j}$ proporcionados no supera $10^{9}$.

Salida

Imprime $(N-1)$ líneas.

Para cada $1 \leq i \leq (N-1)$, en la línea $i$ imprime la carga vial de la carretera que conecta la ciudad $i$ y la ciudad $(i+1)$.

Ejemplos

Entrada 1

4 2
1 3 4
1 3 3
2 4 1

Salida 1

9
6
1

Nota

El número de vehículos que utilizan la carretera diariamente se puede calcular de la siguiente manera:

• Carretera que conecta la ciudad 1 y la ciudad 2: $3 + 0 = 3$ vehículos
• Carretera que conecta la ciudad 2 y la ciudad 3: $3 + 1 = 4$ vehículos
• Carretera que conecta la ciudad 3 y la ciudad 4: $0 + 1 = 1$ vehículo

La carga vial de cada carretera se puede calcular de la siguiente manera:

• Carga vial de la carretera entre la ciudad 1 y la ciudad 2: Como solo hay un carril, $3^{2} = 9$
• Carga vial de la carretera entre la ciudad 2 y la ciudad 3: Como se explicó anteriormente, $6$
• Carga vial de la carretera entre la ciudad 3 y la ciudad 4: Como solo hay un vehículo, sin importar por qué carril circule, $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$