바이토닉 투어

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

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

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

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

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

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

• $1\leq T\leq100\,000$.
• $2\leq N\leq2000$.
• $-1\le W_{ij}\le {10}^{}$이며, 은 간선이 없음을 뜻한다.