Connect The Chains

A *chain* of length $M$ is a graph on $M$ vertices, such that its only edges are of the form $(i, i+1)$ for each $1 \leq i \lt M$. You are given $N$ chain graphs, each of length $M$. Vertex $j$ of the $i$-th chain graph has the integer $A_{i, j}$ written on it. You would like to merge all these chains into a single tree of $N\cdot M$ vertices, by adding $N-1$ extra edges. What is the **minim