我们考虑生成一棵生成树的过程，本质上相当于是选择一些生成树拼起来，而两个生成树拼起来的代价就是把拼接点的权值乘上点的个数积。

于是可以考虑一个 $dp$ ，设 $dp[S][u]$ 表示一个点集 $S$ 组成的根为 $u$ 的树可以得到的最小权值。

于是我们考虑枚举一个子集来进行转移，也就是对于一个子集 $T$ ，我们可以枚举一下这个树的根，然后转移：

$$dp[S][u] = \min\{dp[S][u] , dp[T][v] + dp[S \setminus T][u] + (n - siz[T]) \times siz[T] \times w_{u,v}\}$$

但是可以发现，直接这么转移是 $O(3^n n^2)$ 的，需要枚举子集再枚举一个子集中的点，如何优化呢？

我们考虑 $dp[S][u]$ 的转移点是什么，也就是设 $pd[S][u]$ 表示在这个状态下的

$$\min_{v\in S}\{dp[S][v] + siz[S] \times (n - siz[S]) \times w_{u,v}\}$$

在算出 $dp[S]$ 的值后就可以把每个状态对应的决策点 $v$ 给算出。不难发现，我们相当于把 $O(n^2)$ 的时间复杂度放到了每个状态上，从 $O(3^n n^2)$ 变成了 $O(3^n n)$。

总的复杂度变成了 $O(3^n n + n^22^n)$

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "string"

using namespace std;
#define MAXN 16
//#define int long long
#define rep( i , a , b ) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per( i , a , b ) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all( x ) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353

int n;
int G[MAXN][MAXN];
ll dp[1 << MAXN][MAXN] , pd[1 << MAXN][MAXN];

void solve( ) {
	cin >> n;
	rep( i , 1 , n ) rep( j , i + 1 , n ) scanf("%d",&G[i][j]) , G[j][i] = G[i][j];
	memset( pd , 0x3f , sizeof pd ) , memset( dp , 0x3f , sizeof dp );
	rep( S , 1 , ( 1 << n ) - 1 ) {
		int sz = __builtin_popcount( S );
		rep( i , 1 , n ) if( S & ( 1 << i - 1 ) ) {
			if( sz == 1 ) dp[S][i] = 0;
			for( int T = ( S - 1 ) & S ; T ; T = ( T - 1 ) & S ) if( ~T & ( 1 << i - 1 ) )
				dp[S][i] = min( dp[S][i] , pd[T][i] + dp[S ^ T][i] );
		}
		rep( i , 1 , n ) {
			rep( v , 1 , n ) if( S & ( 1 << v - 1 ) ) if( G[i][v] )
				pd[S][i] = min( pd[S][i] , 1ll * sz * ( n - sz ) * G[i][v] + dp[S][v] );
		}
	}
	ll res = 0x3f3f3f3f3f3f3f3f;
	rep( i , 1 , n ) res = min( res , dp[( 1 << n ) - 1][i] );
	cout << res << endl;
}

signed main( ) {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve( );
}