DFS Order

Bessie has a simple undirected graph with vertices labeled $1$ to $N$ ($2 \le N \le 750$). She generates a depth-first search (DFS) order of the graph by calling dfs(1) as defined in the code below. Each adjacency list adj[i] ($1 \le i \le N$) may be permuted arbitrarily before the search starts, so one graph can have several possible DFS orders.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // adjacency list
vector<int> dfs_order;

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    dfs_order.push_back(x);
    for (int y : adj[x]) dfs(y);
}

For every pair of vertices $(i,j)$ with $1 \le i < j \le N$, you are given an integer $a_{i,j}$ ($0 < |a_{i,j}| \le 1000$).

• If $a_{i,j} > 0$, edge $(i,j)$ is not in the graph and can be added for cost $a_{i,j}$.
• If $a_{i,j} < 0$, edge $(i,j)$ is in the graph and can be removed for cost $-a_{i,j}$.

Find the minimum total cost to change the graph so that $[1, 2, \dots, N]$ is a possible DFS order.

The first line contains $N$. Then $N-1$ lines follow. The $(j-1)$th line contains $a_{1,j}, a_{2,j}, \dots, a_{j-1,j}$, separated by spaces.

Print the minimum total cost to change the graph so that $[1, 2, \dots, N]$ is a possible DFS order.