워프 속도 II

멀지 않은 미래, 우주 엔지니어들이 우주를 이동하는 새로운 기술을 발명하고 이를 워프 드라이브라고 부른다. 워프 드라이브는 공간의 일정 구간을 접어서 우주선이 그 접힌 공간을 단 한 번의 홉(hop)으로 건너가게 함으로써 빛보다 빠르게 이동하게 해 준다. 한 지점에서 다른 지점으로 이동하려면, 워프 드라이브를 장착한 우주선은 여러 번의 홉을 연달아 수행해야 할 수도 있다.

한 번의 홉에 드는 에너지는 워프 드라이브의 현재 상태(state, 구성)에 따라 달라지며, 워프 드라이브를 한 상태에서 다른 상태로 전환하는 데에도 에너지가 든다.

당신은 전투용 우주선의 엔지니어로서, 각 이동에 드는 에너지가 최소가 되도록 워프 드라이브를 구성해야 한다. 이동마다 홉의 순서가 주어지며, 전체 에너지가 최소가 되도록 각 홉마다 상태를 하나씩 골라야 한다.

두 개의 에너지 표가 주어진다. 첫 번째 표는 임의의 두 상태 사이를 전환하는 데 드는 에너지를, 두 번째 표는 각 상태에서 각 홉을 수행하는 데 드는 에너지를 나타낸다. 각 홉 순서에 대해 최소 총 에너지와 그에 대응하는 상태 순서를 출력하는 프로그램을 작성하라.

입력은 표준 입력으로 주어지며, 빈 줄로 구분된 네 부분으로 구성된다.

첫 번째 부분 — 크기. 공백으로 구분된 두 정수가 한 줄에 주어진다.

• $N$ ($1 \le N \le 100$): 워프 드라이브 상태의 개수이며, 상태 id는 $0$부터 $N-1$까지이다. 상태 $0$은 대기(idle) 상태로, 오직 이 상태에서만 어떤 홉도 수행할 수 없으며, 모든 상태 순서의 기본 시작·종료 상태이다.
• $H$ ($1 \le H \le 1000$): 홉 종류의 개수이며, 홉 id는 $0$부터 $H-1$까지이다.

두 번째 부분 — 상태 전환 표. $N$개의 줄이 있고, 각 줄에는 $1$ 이상 $100$ 이하의 정수 $N$개가 있다. $i$행 $j$열의 값은 워프 드라이브를 상태 $i$에서 상태 $j$로 전환하는 데 드는 에너지이다(행과 열은 $0$부터 센다).

세 번째 부분 — 홉 에너지 표. $N$개의 줄이 있고, 각 줄에는 $1$ 이상 $100$ 이하의 정수 $H$개가 있다. $s$행 $c$열의 값은 상태 $s$에서 홉 $c$를 수행하는 데 드는 에너지이다($0$부터 센다). 첫 번째 줄(상태 $0$, 대기 상태)은 모두 $0$인데, 대기 상태에서는 어떤 홉도 수행할 수 없기 때문이다.

네 번째 부분 — 홉 순서. $1$개 이상 $1000$개 이하의 줄이 있으며, 각 줄은 하나의 홉 순서이다. 한 순서는 $1$개 이상 $1000$개 이하의 홉을 담으며, 각 홉은 $0$부터 $H-1$까지의 홉 id로 공백으로 구분된다.

네 번째 부분의 각 홉 순서에 대해 두 줄을 출력한다.

• 가능한 최소 총 에너지.
• 각 홉에 대응하는 상태 순서(홉 순서와 길이가 같다). 상태는 공백으로 구분한다.

한 이동의 총 에너지는 대기 상태 $0$에서 첫 번째로 선택한 상태로 전환하는 에너지, 각 선택한 상태에서의 홉 에너지, 연속한 선택 상태 사이의 전환 에너지, 그리고 마지막으로 선택한 상태에서 대기 상태 $0$으로 돌아가는 전환 에너지를 모두 더한 값이다.

같은 최소 에너지를 내는 상태 순서가 여럿이면, 상태 id를 왼쪽부터 비교했을 때 가장 작은(사전순으로 가장 앞서는) 순서를 출력한다.

첫 번째 예제의 홉 순서 0 4를 생각해 보자. 최적의 상태 순서는 3 2이며 총 에너지는 $9$이다. 전환 $0 \to 3$, $3 \to 2$, $2 \to 0$이 $1 + 1 + 2 = 4$이고, 상태 $3$에서 홉 $0$을, 상태 $2$에서 홉 $4$를 수행하는 데 $4 + 1 = 5$가 들어 합이 $4 + 5 = 9$이다.

홉 순서 1 2 3 2의 경우 최적의 상태 순서는 1 1 2 3이고 총 에너지는 $23$이다.