Minimum Cycle Cover in Directed Graph

In city W, a severe pneumonia outbreak requires that every community (block) be inspected weekly. The city has \(n\) blocks and \(m\) distinct directed roads connecting them. There is no road that starts and ends at the same block, and the network is weakly connected (i.e. if the directions are ignored, the graph is connected). Traveling on each road consumes some amount of fuel.

You have an infinite number of workers available. You must split the \(n\) blocks into disjoint groups and assign each group to one worker. For each worker, you choose an ordering of the blocks in his group. Every week, the worker visits the blocks strictly in that order and then repeats the cycle indefinitely. Note that the worker only inspects the blocks that you explicitly assign to him. Although he may pass through other blocks when traveling between two consecutive assigned blocks, he does not inspect those intermediate blocks. In order to avoid redundancy, every block must be inspected by exactly one worker (i.e. it appears in the assignment of exactly one worker). A block may appear more than once in a cycle if needed.

The cost incurred by a worker is defined as follows:

• If the worker is assigned exactly one block \(u\), then his weekly cost is \(a_u\) (a given staying cost for block \(u\)).
• If the worker is assigned more than one block then his cost is the sum of the fuel costs of the roads along a cycle that starts at the first block, visits the assigned blocks in the given order, and finally returns to the starting block. Note that the path chosen between consecutive assigned blocks must be a valid directed path in the road network.

The goal is to cover all blocks while minimizing the total weekly cost, under the assumption that there is an unlimited number of workers available.

Hint: For each pair of blocks \(i\) and \(j\), let \(d(i,j)\) be the minimum fuel cost required to travel from block \(i\) to block \(j\) (if a path exists). Then, for every block \(i\) we consider two possibilities:

• Cover block \(i\) by a worker assigned only to \(i\) at a cost of \(a_i\).
• Cover block \(i\) as part of a cycle with other blocks at a cost of \(d(i,j)\) for some chosen edge \((i,j)\).

This can be modeled as a minimum cycle cover problem on a complete directed graph with \(n\) nodes where for \(i \neq j\) the edge weight from \(i\) to \(j\) is \(d(i,j)\) and the self-loop weight for node \(i\) is \(a_i\). The answer is the minimum total cost of a cycle cover of this graph.

Formally: Given \(n\) and \(m\), an array \(a = [a_1, a_2, \dots, a_n]\) and \(m\) directed roads of the form \((u, v, w)\), find the minimum cost to choose a cycle cover such that every block is included exactly once, where for \(i\neq j\) the cost of edge \(i\to j\) is the minimum fuel cost from \(i\) to \(j\) (computed via, e.g., the Floyd–Warshall algorithm) and the cost of a cycle covering a single block \(i\) is \(a_i\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq N,\ 1 \leq m \leq M)\) — the number of blocks and the number of directed roads, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the cost if a worker is assigned only block \(i\).

Then \(m\) lines follow. Each line contains three integers \(u, v, w\) indicating that there is a directed road from block \(u\) to block \(v\) with fuel cost \(w\) \(\;(1 \leq u,v \leq n,\ u \neq v)\).

You can assume that the underlying undirected graph is connected.

outputFormat

Output a single integer — the minimum total weekly cost to cover all the blocks.

sample

3 3
5 2 7
1 2 3
2 3 4
3 1 2

9