아이들을 위하여

이 문제는 대회 1분 뒤 모든 팀에 보낸 정정 공지로 대회에서 철회되었다.

철회 이유는 대회 24시간 전 시점에 출제팀이 해답을 하나만 가지고 있었기 때문이다. 우리는 두 명 이상의 출제자가 독립적으로 확인한 뒤에야 문제를 진행하는 것을 강하게 선호한다.

전국 규모의 자선단체 Won't Someone Think of the Children이 유명 홍보대사를 동해안에서 서해안까지 잇는 홍보 투어에 보낸다. 여느 자선단체처럼 이 단체도 자금이 넉넉하지 않아서, 서해안 사무소에서 동해안의 마지막 기자회견장까지 홍보대사의 이동 경비를 신중하게 계획해야 한다.

이 단체의 지역 사무소들은 투어 중 홍보대사가 각 도시를 방문하는 데 쓸 비용을 모으려고 약정금과 기부금을 받아 왔다. 본부는 홍보대사가 중간 도시 중 어디를 방문하는지 약속하지 않았지만, 지역에서 모은 돈이 동서 횡단 여정의 비용에 보탬이 되기를 바란다. 지역 사무소의 도움이 없다면 본부는 홍보대사를 최종 목적지까지 보낼 여력이 있을지 확신하지 못한다.

여행 경비는 단계별로 치러진다. 홍보대사는 다음 도시까지의 교통비를 감당할 돈이 있을 때에만 한 도시에서 다른 도시로 이동할 수 있다. 도시에 도착하면 그 도시에 모인 돈을 모두 받아, 이후 구간의 경비에 쓴다. 홍보대사는 같은 도시를 한 번만 방문할 수 있다.

홍보대사를 초청한 도시 목록, 각 도시가 모은 금액, 도시 쌍 사이의 이동 경비가 주어질 때, 여행 중 어느 구간의 경비도 치르지 못하는 일 없이 끝까지 갈 수 있도록 여행 시작 시점에 본부가 제공해야 하는 금액의 최솟값을 구하라.

입력은 하나 이상의 데이터 셋으로 이루어진다. 각 데이터 셋은 도시 수 $N$을 나타내는 정수 한 개가 적힌 줄로 시작한다. $2 \leq N < 24$이다. $N$이 0이면 입력이 끝난다.

도시는 $0 \ldots N-1$ 범위의 번호로 구분한다. 도시 0은 본부이자 출발지이다. 도시 $N-1$은 최종 목적지이다.

이어지는 $N-2$개의 줄에는 각각 $0 \ldots 10\,000$ 범위의 정수가 하나씩 적혀 있으며, 이는 도시 $1 \ldots N-2$가 모은 금액이다. 도시 $N-1$의 금액은 상관없고, 도시 0에서 제공해야 할 금액이 구하려는 값이다.

그 뒤의 각 줄에는 정수 $i$, $j$, $c$가 하나씩 적혀 있다. $i$와 $j$는 서로 다른 도시로 $0 \ldots N-1$ 범위이고, $c$는 두 도시 사이의 이동 경비이며 $0 < c < 10\,000$이다. 경비는 양방향이 같다. 이 줄은 최소 1개, 최대 $N(N-1)/2$개가 있다. 목록의 끝은 $i$, $j$, $c$가 모두 음수인 줄로 표시된다.

데이터 셋마다 한 줄을 출력하라.

도시 0에서 도시 $N-1$에 도달할 수 있으면, 도시 $N-1$에 확실히 도달하기 위해 도시 0에서 대상자에게 주어야 하는 금액의 최솟값을 출력하라.

도시 0에서 도시 $N-1$에 도달할 수 없으면 $-1$을 출력하라.