显然，答案等于这棵树每条边长度之和的两倍。
钦定以 \(1\) 为根，考虑逐个确定每个点的位置。
假设目前已经确定了 \(1\sim(u-1)\) 的位置，我们希望找到 \(u\) 的位置。或者更具体地，我们希望求出节点 \(u\) 到已经确定的树的距离，并往树上挂一条这么长的链。
节点 \(u\) 到 \(1\leftrightarrow v\) 路径的距离为 \(\frac{1}{2}(\operatorname{dis}(1,u)+\operatorname{dis}(1,v)-\operatorname{dis}(u,v))\)，这一距离同时也是节点 \(u\) 到 \(\operatorname{LCA}(u,v)\) 的距离。我们找到使得这一距离取到最小值的点 \(v\)（也就是 \(\operatorname{LCA}(u,v)\) 最深的 \(v\)），则只需要在 \(\operatorname{LCA}(u,v)\) 处挂一条长度为 \(\frac{1}{2}(\operatorname{dis}(1,u)+\operatorname{dis}(1,v)-\operatorname{dis}(u,v))\) 的链，链的另一端即为点 \(u\) 的位置。
统计我们挂的每一条链的长度，加起来乘以二即为答案。
提交上去会发现只拿到了子任务三和子任务四的 \(34\) 分，为什么？发现被可爱的出题人摆了一道。数据范围只说了输入的距离矩阵都是整数，并没有说每条边的长度都是整数，因此可以构造出以下数据：
可以发现距离矩阵都是整数，但是边的长度可以是半整数，如果计算距离时使用整数除法就会算错。一个简单的解决方法是在输入时将距离矩阵所有元素乘以二，这样答案就是这棵树所有边长度之和，而且不会涉及到浮点数了。
时间复杂度 \(O(n^2)\)。
// Problem: P15349 [TOIP 2025] 巡视农场
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P15349
// Memory Limit: 2048 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {uniform_int_distribution<int> dist(L, R);return dist(rnd);
}template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}template<int mod>
inline unsigned int down(unsigned int x) {return x >= mod ? x - mod : x;
}template<int mod>
struct Modint {unsigned int x;Modint() = default;Modint(unsigned int x) : x(x) {}friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}friend Modint operator/(Modint a, Modint b) {return a * ~b;}friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}friend Modint operator~(Modint a) {return a ^ (mod - 2);}friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}friend Modint& operator++(Modint& a) {return a += 1;}friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}friend Modint& operator--(Modint& a) {return a -= 1;}friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}friend bool operator==(Modint a, Modint b) {return a.x == b.x;}friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};const ll N = 5e3 + 5, inf = 0x3f3f3f3f3f3f3f3f;ll n, a[N][N], ans;int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];rep(i, 1, n) rep(j, 1, n) a[i][j] *= 2;ans += a[1][2];rep(i, 3, n) {ll now = +inf;rep(j, 2, i - 1) chkmin(now, (a[1][i] + a[i][j] - a[1][j]) / 2);ans += now;}cout << ans << endl;return 0;
}