Computing MDSST

In this problem, we will consider weighted undirected graphs where all edges have positive weights.

Let $D(G,i,j)$ be the length of the shortest path in graph $G$ between vertex $i$ and vertex $j$.

We are given a complete weighted undirected graph $G$ which consists of $n$ vertices numbered from $1$ to $n$. Among the spanning trees of $G$, the MDSST (Minimum Distance Sum Spanning Tree) is such $T$ for which the value $S(T) = \sum\_{1 \leq i < j \leq n} D(T,i,j)$ is minimum. Your task is to find MDSST of $G$ and print $S(T)$.

The first line contains an integer $n$, the number of vertices in the graph ($2 \le n \le 15$). The $i$-th of the following $n-1$ lines contains $n-i$ integers separated by spaces. The $j$-th integer of this the line is the length of the edge between vertex $i$ and vertex $i+j$.

All the lengths are between $1$ and $10^9$, inclusive.

On the first line, print one integer: the value $S(T)$ for the MDSST you found.