바이토닉 투어

$N$개의 정점으로 이루어진 가중치 무방향 그래프가 주어진다. 정점 $i$와 정점 $j$를 잇는 간선의 가중치는 $W_{ij}$이다. $W_{ij}=-1$이면 해당 간선은 없다.

$1$부터 출발하여 정점 번호가 엄격히 증가하는 순서로 $N$까지 이동한 뒤, 정점 번호가 엄격히 감소하는 순서로 $1$로 돌아오려 한다. 출발점으로 돌아오기 전까지 모든 정점을 정확히 한 번씩 방문해야 하며, 모든 이동에 해당하는 간선이 존재해야 한다. 가능한 방문 순서 중 지나간 간선의 가중치 합이 최소인 것을 아무거나 하나 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $W_{11}\ W_{12}\ \cdots\ W_{1N}$ $W_{21}\ W_{22}\ \cdots\ W_{2N}$ $\vdots$ $W_{N1}\ W_{N2}\ \cdots\ W_{NN}$

각 케이스마다 조건을 만족하는 방문 순서가 없으면 $-1$만 출력한다.

그렇지 않으면 첫째 줄에 최소 총 가중치를 출력하고, 둘째 줄에 출발점으로 돌아오기 전 방문하는 정점 번호 $p_1,p_2,\ldots,p_N$을 공백으로 구분하여 출력한다. $p_1=1$이며, $p_1,p_2,\ldots,p_N$은 $1$부터 $N$까지의 순열이다. 마지막 정점 $p_N$에서 $1$로 돌아가는 간선도 총 가중치에 포함된다. 가능한 답이 여러 개라면 아무거나 출력해도 된다.

• $1\leq T\leq100\,000$.
• $2\leq N\leq2000$.
• $-1\leq W_{ij}\leq10^9$이며, $-1$은 간선이 없음을 뜻한다.
• $W_{ii}=0$이다.
• $W_{ij}=W_{ji}$이다.
• 모든 케이스에 대한 $N^2$의 합은 $4\,000\,000$ 이하이다.