색 뒤집기

무방향 완전 그래프가 주어진다. 모든 노드 쌍은 빨간색 또는 검은색 간선으로 연결되어 있다. 각 간선에는 패널티라고 부르는 정수 값이 있다.

그래프에 연산을 반복 적용하여 빨간 간선만으로 이루어진 스패닝 트리를 만들어야 한다. 즉, 빨간 간선의 개수가 노드 수보다 정확히 1 작아야 하고, 모든 노드가 빨간 간선을 통해 직접 또는 간접으로 연결되어야 한다. 이런 트리를 두 개 이상 만들 수 있다면, 빨간 간선 패널티의 합이 가장 작은 트리를 고른다.

연산 한 번에 노드 하나를 고르고, 그 노드에 연결된 간선의 색을 모두 뒤집는다. 빨간 간선은 검은색이 되고, 검은 간선은 빨간색이 된다.

그림 F-1의 왼쪽 그래프는 첫 번째 데이터셋이다. 노드 3에 연결된 간선의 색을 모두 뒤집고, 이어서 노드 2에 연결된 간선의 색을 모두 뒤집으면 오른쪽 그래프처럼 빨간 간선만으로 이루어진 스패닝 트리가 된다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식이다.

n
e1,2 e1,3 ... e1,n-1 e1,n
e2,3 e2,4 ... e2,n
...
en-1,n

정수 $n$ ($2 \le n \le 300$)은 노드 수이며, 노드는 1부터 $n$까지 번호가 매겨져 있다. 각 $e_{i,k}$ ($1 \le |e_{i,k}| \le 10^5$)는 노드 $i$와 노드 $k$ 사이 간선의 패널티와 처음 색을 나타낸다. 절댓값 $|e_{i,k}|$가 패널티이다. $e_{i,k} > 0$이면 처음에 빨간색, $e_{i,k} < 0$이면 처음에 검은색이다.

입력의 끝은 0이 적힌 줄이다. 데이터셋은 50개를 넘지 않는다.

각 데이터셋마다, 위 연산으로 만들 수 있는 빨간 스패닝 트리 중 패널티 합이 가장 작은 값을 출력한다. 빨간 스패닝 트리를 만들 수 없으면 -1을 출력한다.