Optimal Vertex Coloring Game on a Weighted Graph

Taozi (who paints vertices pink) and Ali (who paints vertices red) are playing an exciting game on a weighted undirected graph \(G=(V,E)\). Each vertex \(v\) has a weight \(w(v)\) and each edge \(e\) has a cost \(c(e)\). The game is played as follows:

1. The two players take turns coloring an uncolored vertex. In each round exactly one vertex is colored. Once colored, a vertex cannot be recolored.
2. There is an even number \(N\) of vertices, so after \(N/2\) rounds each player gets exactly \(N/2\) vertices.
3. For a player’s set \(S\) of vertices, the score is computed as \[ \sum_{v\in S} w(v) + \sum_{\substack{e=(u,v)\in E\\ u,v\in S}} c(e). \]

Since Taozi won the coin toss (rock–paper–scissors), Taozi colors first. Both players play optimally to maximize the difference between their own score and their opponent’s score. Assuming both adopt optimal strategies, compute the final difference (i.e. Taozi's score minus Ali's score).

Note: All formulas are written in LaTeX format. The vertices in the input are numbered from 1 to \(N\).

inputFormat

The first line contains two integers \(N\) and \(M\), where \(N\) (even) is the number of vertices and \(M\) is the number of edges.

The second line contains \(N\) integers: \(w(1), w(2), \dots, w(N)\) representing the weight of each vertex.

Then \(M\) lines follow, each containing three integers \(u\), \(v\) and \(c\) which describe an undirected edge between vertices \(u\) and \(v\) with cost \(c\). (Vertices are 1-indexed.)

outputFormat

Output a single integer representing the final difference: (Taozi's score) minus (Ali's score) when both play optimally.

sample

2 0
5 3

2