题目描述
d__ 和 d__ 要 t__ t__ 。有一张 $n$ 个点，$m$ 条边的无向图。现在小 q 想要把每条边定向，使得不管 d__ 和 d__ 在哪两个点，d__ 都能顺着这些有向边找到 d__（即强连通）。小 q 想要知道代价最小的方案，注意每条无向边的两种定向方式的代价不同。
输入格式
第一行一个正整数 $n$ 。
接下来 $n$ 行，每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个数代表 $a_{i,j}$ ，表示定向为 $i$ 到 $j$ 的有向边的代价。如果不存在 $i,j$ 之间的边， $a_{i,j}=-1$ 。保证 $a_{i,i}=-1$ 。
输出格式
一行一个整数，表示最小代价。如果无解，输出 $-1$ 。
样例输入 1
4 -1 3 2 -1 3 -1 7 7 5 9 -1 9 -1 6 7 -1
样例输出 1
27
样例输入 2
6 -1 1 2 -1 -1 -1 3 -1 4 -1 -1 -1 5 6 -1 0 -1 -1 -1 -1 0 -1 6 5 -1 -1 -1 4 -1 3 -1 -1 -1 2 1 -1
样例输出 2
-1
数据范围
保证 $n\leq 18$ 。
subtask1(30pts)：保证 $n\leq 7$ 。
subtask2(30pts)：保证 $n\leq 12$ 。
subtask3(20pts)：保证 $n\leq 16$ 。
subtask4(20pts)：无特殊限制。