여행

Byteasar는 최근 자전거 여행의 즐거움에 빠졌다. 그는 휴가 $k$일 동안 Byteotia의 시골길을 자전거로 달리려고 한다. 매일 서로 다른 경로로 여행하고 싶어 한다. 또한 여행의 난이도를 점차 높이고 싶어서, 각 여행은 바로 전날의 여행보다 짧지 않아야 한다. 구체적으로 $i$일째에는 Byteotia의 마을들을 지나는 가능한 경로 중 $i$번째로 짧은 경로를 따라간다. 휴가의 $k$일째에 떠나는 마지막 여행의 길이를 구하라.

첫 줄에 공백으로 구분된 세 정수 $n$, $m$, $k$가 주어진다. 여기서 $1 \le n \le 40$, $1 \le m \le 1000$, $1 \le k \le 10^{18}$이다. 이어지는 $m$개의 줄에는 도로가 한 줄에 하나씩 주어진다. 각 줄에는 공백으로 구분된 세 정수 $u$, $v$, $c$가 있으며, $1 \le u, v \le n$, $u \ne v$, $1 \le c \le 3$이다. 이는 마을 $u$에서 마을 $v$로 가는 길이 $c$킬로미터의 일방통행 도로가 있다는 뜻이다. 같은 두 마을 사이에 도로가 여러 개 있을 수 있다. 경로는 어느 마을에서 시작해 어느 마을에서 끝나도 되며, 같은 마을이나 도로를 여러 번 지나도 된다.

배점의 75%에 해당하는 테스트에서는 $n \le 15$, $m \le 200$, $k \le 10^{12}$이다. 배점의 50%에 해당하는 부분 문제에서는 모든 도로에 대해 $c = 1$이다. 그중 배점의 25%에 해당하는 부분 문제에서는 추가로 $k \le 1\,000\,000$이다.

한 줄에 $k$번째로 짧은 경로의 길이를 출력한다. 서로 다른 경로가 $k$개보다 적으면 $-1$을 출력한다.

길이가 1인 경로: 1 → 2, 5 → 3, 4 → 5.

길이가 2인 경로: 2 → 3, 3 → 4, 4 → 5 → 3.

길이가 3인 경로: 4 → 6, 1 → 2 → 3, 3 → 4 → 5, 5 → 3 → 4.

길이가 4인 경로 중 11번째로 짧은 것은 예를 들어 5 → 3 → 4 → 5이다.