호빗, 또는 왕복 여행

빌보는 평범하지 않은 여행을 마치고 집으로 돌아와, 그 이야기를 《서부 변경의 붉은 책》이라는 제목의 책으로 쓰기로 했다. 여행 중에 그는 안개산맥 아래의 동굴을 찾았고, 숲속 요정들의 감옥에 갇혔으며, 외로운 산에서 용을 만났다. 그 밖에도 여러 곤경을 겪었다.

빌보가 방문한 흥미로운 장소는 모두 $n$곳이다. 흥미로운 장소와 빌보의 집은 모두 한 직선 위에 있다. 집은 좌표 $0$에 있고, $i$번째 장소는 집에서 $x_i$킬로미터 떨어져 있다. 두 장소 $i$와 $j$ 사이에는 다른 흥미로운 장소를 거치지 않는 숨겨진 길이 하나씩 있다. 이 길의 길이는 $|x_j - x_i|$이고, 위험도는 $c_{i,j}$이다. $i$번째 장소와 집 사이에도 숨겨진 길이 있는데, 길이는 $x_i$, 위험도는 $0$이다.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 1000$). 둘째 줄에는 $n$개의 정수 $x_i$가 주어진다 ($1 \le x_i \le 10^9$). $x_i$는 $i$번째 장소가 집에서 떨어진 거리(킬로미터)이다. 모든 $x_i$는 서로 다르다. 이어서 $n$개의 줄에 각각 $n$개의 정수가 주어진다. $i$번째 줄의 $j$번째 수는 $c_{i,j}$로, 장소 $i$와 $j$ 사이 숨겨진 길의 위험도이다 ($0 \le c_{i,j} \le 10^6$, $c_{i,j} = c_{j,i}$, $c_{i,i} = 0$).

첫째 줄에 빌보의 여행 길이와 위험도를 공백으로 구분해 출력한다. 둘째 줄에는 빌보가 방문하는 흥미로운 장소의 번호를 방문 순서대로 $n$개 출력한다.