为什么费用流不拆点过不了，就是一个点向它的下一个点连两条边，一条边容量为 $1$，费用为 $-w$, 另一条边容量为 inf，费用为 $0$。

struct MCFGraph {
	struct Edge {
		int v;
		long long c, f;
		Edge(int v, long long c, long long f) : v(v), c(c), f(f) {}
	};
	const int n;
	std::vector<Edge> e;
	std::vector<std::vector<int>> g;
	std::vector<long long> h, dis;
	std::vector<int> pre;
	bool dijkstra(int s, int t) {
		dis.assign(n, std::numeric_limits<long long>::max());
		pre.assign(n, -1);
		std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> que;
		dis[s] = 0;
		que.emplace(0, s);
		while (!que.empty()) {
			long long d = que.top().first;
			int u = que.top().second;
			que.pop();
			if (dis[u] < d) continue;
			for (int i : g[u]) {
				int v = e[i].v;
				long long c = e[i].c;
				long long f = e[i].f;
				if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
					dis[v] = d + h[u] - h[v] + f;
					pre[v] = i;
					que.emplace(dis[v], v);
				}
			}
		}
		return dis[t] != std::numeric_limits<long long>::max();
	}
	MCFGraph(int n) : n(n), g(n) {}
	void addEdge(int u, int v, int w, int c) {
		if (c < 0) {
			g[u].push_back(e.size());
			e.emplace_back(v, 0, c);
			g[v].push_back(e.size());
			e.emplace_back(u, w, -c);
		} else {
			g[u].push_back(e.size());
			e.emplace_back(v, w, c);
			g[v].push_back(e.size());
			e.emplace_back(u, 0, -c);
		}
	}
	std::pair<long long, long long> flow(int s, int t) {
		long long flow = 0;
		long long cost = 0;
		h.assign(n, 0);
		while (dijkstra(s, t)) {
			for (int i = 0; i < n; ++i) h[i] += dis[i];
			long long aug = std::numeric_limits<long long>::max();
			for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
			for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
				e[pre[i]].c -= aug;
				e[pre[i] ^ 1].c += aug;
			}
			flow += aug;
			cost += (long long)(aug) * h[t];
		}
		return std::make_pair(flow, cost);
	}
};

int w[55][55];
void solve(){
    int n,m,a,b,c;
    cin>>n;
    auto idx=[&](int x,int y)
    {
        return (x-1)*n+y;
    };
    while(cin>>a>>b>>c)
    {
        if(!a&&!b&&!c)break;
        w[a][b]=c;
    }
    MCFGraph e(5001);
    e.addEdge(0,1,2,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i+1<=n)
            {
                e.addEdge(idx(i,j),idx(i+1,j),1,-w[i+1][j]);
                e.addEdge(idx(i,j),idx(i+1,j),int_inf,0);
            }
            if(j+1<=n)
            {
                e.addEdge(idx(i,j),idx(i,j+1),1,-w[i][j+1]);
                e.addEdge(idx(i,j),idx(i,j+1),int_inf,0);
            }
        }
    }
    e.addEdge(idx(n,n),5000,int_inf,0);
    auto[f,cc]=e.flow(0,5000);
    writeln(w[1][1]-e.flow(0,5000).second);
}