**  재귀를 통해 각 정점에서 방문하지 않은 정점 중 최소 길이인 값을 더해가고 그 거리들을 반환하여 최단거리를 구합니다.
모든 정점에 대해서  이 방법을 사용합니다. **


using namespace std;

void loadCost();
double minDistClac(const vector<vector<double> >& dist, vector<bool> visit, double curDist, const int& cnt, int v);


double minDistClac(const vector<vector<double> >& dist, vector<bool> visit, double curDist, const int& cnt, int v)
{
    visit[v] = true;
    double minDist = ~(1<<31);
    int minV = 0;
    for(int i = 0; i < cnt; i++)
    {
        if(!visit[i] && minDist >= dist[v][i])
        {
            minDist = dist[v][i];
            minV = i;
        }
    }

    if(minDist == ~(1<<31)) return curDist;
    else return curDist + minDistClac(dist, visit, minDist, cnt, minV);
}


void loadCost()
{

    int n;
    scanf("%d", &n);

    vector<vector<double>> dist(n);
    vector<bool> visit(n, false);

    for(auto &e : dist)
    {
        for(int i = 0; i < n; i++)
        {
            double cost;
            cin >> cost;
            e.push_back(cost);
        }
    }

    double minDist = ~(1<<31);

    for(int i = 0; i < n; i++)
    {
        minDist = min(minDist, minDistClac(dist, visit, 0.0, n, i));
    }

    printf("%.10f\n", minDist);

}

int main()
{
    int c;
    cin >> c;
    while(c--)
    {
        loadCost();
    }

    return 0;
}