#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int maxm = 5500; const int maxn = 110; int fa[maxn]; int N; struct edge { int x, y, w; }; bool cmp(edge a, edge b) { return a.w < b.w; } vector<edge> v; int getfather(int x) { if(x==fa[x]) return x; else return fa[x] = getfather(fa[x]); } int krucal() { int cnt = N; int ans = 0; int edgeSize = v.size(); for(int i = 1; i <= N; i++) fa[i] = i; for(int i=0; i < edgeSize; i++) { int f1 = getfather(v[i].x); int f2 = getfather(v[i].y); if(f1 != f2) { fa[f1] = f2; cnt--; ans += v[i].w; if(cnt==1) break; } } return ans; } int main() { edge tmp; int w; while(scanf("%d", &N)!=EOF) { v.clear(); for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { scanf("%d", &w); if(i!=j || w>0) { tmp.x = i; tmp.y = j; tmp.w = w; v.push_back(tmp); } } } sort(v.begin(), v.end(), cmp); int result = krucal(); printf("%d ", result); } return 0; }