Toutes les cartes mènent à une seule destination : « SoleMap », la carte de navigation de nouvelle génération de Hyundai AutoEver.

Tout le monde a déjà vu quelqu'un en difficulté en conduisant sur une route inconnue, en prenant un mauvais embranchement ou en se trompant de voie. Même avec un système de navigation, il est souvent difficile de faire correspondre mentalement l'écran du GPS avec la route réelle. SoleMap est la carte de navigation de nouvelle génération que Hyundai AutoEver développe pour résoudre ces désagréments. Le nom « SoleMap » combine l'adjectif « Sole » (qui signifie « unique ») et « Map » (carte), soulignant ainsi l'idée d'intégration. L'objectif est d'intégrer SoleMap dans les systèmes de navigation réels d'ici 2024.

La structure routière du « Pays de la Ligne Droite » peut être modélisée comme $N$ villes disposées en ligne droite, où pour tout $1 \leq i \leq (N-1)$, la ville $i$ et la ville $i+1$ sont directement reliées par une route bidirectionnelle à $w_{i}$ voies. Dans ce pays, il y a chaque jour $x_{j}$ véhicules se déplaçant de la ville $u_{j}$ à la ville $v_{j}$. Par conséquent, un total de $\sum_{j} x_{j}$ véhicules circulent quotidiennement. Bien que l'itinéraire soit unique, le temps de trajet peut varier en fonction des voies utilisées en raison de la congestion. Les systèmes de navigation classiques, qui ne distinguent pas les voies, ne sont donc pas d'une grande aide.

Kipa, le président du Pays de la Ligne Droite, a introduit SoleMap à titre expérimental. La nouvelle selon laquelle le système de navigation indique efficacement les voies les plus rapides s'est rapidement répandue, et tous les systèmes de navigation du pays sont devenus des SoleMap. Craignant que l'augmentation du trafic automobile due à SoleMap ne provoque l'effondrement des routes, Kipa a chargé Hyundai AutoEver de calculer une valeur appelée « charge routière ».

Heureusement, Kipa ayant étudié les mathématiques et l'ingénierie avant de devenir président, il a défini rigoureusement la charge routière afin d'éviter aux techniciens de devoir créer eux-mêmes des indicateurs complexes. Pour chaque route, la charge routière est définie comme suit : étant donné $c$ véhicules utilisant quotidiennement la route et $w$ voies disponibles, il s'agit de la valeur minimale de la somme des carrés du nombre de véhicules par voie, lorsque les $c$ véhicules sont répartis de manière optimale entre les $w$ voies.

Par exemple, si $c = 4$ et $w = 3$ pour une route donnée, les véhicules peuvent être répartis comme suit :

• Si les 4 véhicules empruntent la même voie : $4^{2} + 0^{2} + 0^{2} = 16$
• Si 3 véhicules empruntent une voie et 1 véhicule une autre : $3^{2} + 1^{2} + 0^{2} = 10$
• Si 2 véhicules empruntent une voie et 2 véhicules une autre : $2^{2} + 2^{2} + 0^{2} = 8$
• Si 2 véhicules empruntent une voie, 1 véhicule une deuxième et 1 véhicule une troisième : $2^{2} + 1^{2} + 1^{2} = 6$

La valeur minimale, 6, est la charge routière.

En tant que programmeur de SoleMap, votre mission est de calculer la charge routière de chaque route en fonction de la situation du trafic, et ainsi de viser une promotion !

Entrée

La première ligne contient deux entiers $N$ et $M$ séparés par un espace, représentant le nombre de villes et le nombre d'informations sur les véhicules circulant dans le pays. ($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)

La deuxième ligne contient $(N-1)$ entiers $w_{1}, w_{2}, \cdots, w_{N-1}$ séparés par des espaces. ($1 \leq w_{i} \leq 10^{9}$) Cela signifie que pour chaque $1 \leq i \leq (N-1)$, la route reliant la ville $i$ à la ville $i+1$ possède $w_{i}$ voies.

Les $M$ lignes suivantes contiennent les informations sur le trafic. Pour chaque $1 \leq j \leq M$, la $(j+2)$-ième ligne contient $u_{j}$, $v_{j}$ et $x_{j}$ séparés par des espaces. ($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$) Cela signifie qu'il y a $x_{j}$ véhicules se déplaçant quotidiennement de la ville $u_{j}$ à la ville $v_{j}$.

La somme de tous les $x_{j}$ donnés ne dépasse pas $10^{9}$.

Sortie

Affichez $(N-1)$ lignes.

Pour chaque $1 \leq i \leq (N-1)$, la $i$-ième ligne doit contenir la charge routière de la route reliant la ville $i$ à la ville $i+1$.

Exemples

Entrée 1

4 2
1 3 4
1 3 3
2 4 1

Sortie 1

9
6
1

Remarque

Le nombre de véhicules utilisant chaque route quotidiennement peut être calculé comme suit :

• Route reliant la ville 1 et la ville 2 : $3 + 0 = 3$ véhicules
• Route reliant la ville 2 et la ville 3 : $3 + 1 = 4$ véhicules
• Route reliant la ville 3 et la ville 4 : $0 + 1 = 1$ véhicule

La charge routière de chaque route peut être calculée comme suit :

• Charge routière de la route entre la ville 1 et la ville 2 : Comme il n'y a qu'une seule voie, $3^{2} = 9$
• Charge routière de la route entre la ville 2 et la ville 3 : Comme expliqué précédemment, 6
• Charge routière de la route entre la ville 3 et la ville 4 : Comme il n'y a qu'un seul véhicule, peu importe la voie choisie, $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$