Farmer John은 농장에 전화선을 설치하려고 합니다. 하지만 전화 회사가 협조적이지 않아서 농장을 전화망에 연결하는 데 필요한 일부 케이블 비용을 내야 합니다.

그의 땅에는 외로운 전신주 $N$개($(1 \le N \le 1,000)$)가 흩어져 있으며, 편의상 $1..N$으로 번호가 매겨져 있습니다. 현재 전신주를 연결하는 케이블은 없습니다. 전신주 쌍 $P$개($(1 \le P \le 10,000)$)는 케이블로 연결할 수 있지만, 나머지는 서로 너무 멀리 떨어져 있습니다.

$i$번째 케이블은 서로 다른 전신주 $A_i$와 $B_i$를 연결할 수 있고, 사용하면 길이는 $L_i$ 단위입니다. $(1 \le L_i \le 1,000,000)$입니다. 입력 데이터는 어떤 쌍 {$A_i,B_i$}도 한 번 넘게 주지 않습니다. 전신주 $1$은 이미 전화망에 연결되어 있고 전신주 $N$은 농장에 있습니다. 전신주 $1$과 $N$를 케이블 경로로 연결해야 하며, 나머지 전신주는 사용해도 되고 사용하지 않아도 됩니다.

전화 회사는 Farmer John에게 케이블 $K$개($(0 \le K < N)$)를 무료로 제공하려고 합니다. 그 밖에는 필요한 나머지 케이블 중 가장 긴 것의 길이와 같은 금액을 내야 합니다(각 전신주 쌍은 별도의 케이블로 연결합니다). 추가 케이블이 필요 없다면 금액은 $0$입니다.

Farmer John이 내야 하는 최소 금액을 구하세요.

입력

표준 입력에서 입력을 읽으세요.

• 1번째 줄: 공백으로 구분된 세 정수 $N$, $P$, $K$.

• $2..P+1$번째 줄: $i+1$번째 줄에 공백으로 구분된 세 정수 $A_i$, $B_i$, $L_i$가 주어집니다.

출력

표준 출력에 결과를 쓰세요.

• 1번째 줄: Farmer John이 낼 수 있는 최소 금액인 정수 하나. 농장을 전화 회사에 연결할 수 없다면 $-1$을 출력하세요.

예제

입력 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

출력 1

4

참고

전신주는 5개입니다. 전신주 $1$은 전신주 $4$ 또는 $5$에 직접 연결할 수 없습니다. 전신주 $5$는 전신주 $1$ 또는 $3$에 직접 연결할 수 없습니다. 그 밖의 모든 쌍은 연결할 수 있습니다. 전화 회사는 케이블 하나를 무료로 제공합니다.

전신주 $1$을 $3$에, $3$을 $2$에, $2$를 $5$에 연결하면 Farmer John은 길이가 $4$, $3$, $9$인 케이블이 필요합니다. 전화 회사가 길이 $9$인 케이블을 제공하므로 필요한 나머지 케이블의 최대 길이는 $4$입니다.

문제 제작: Paul Christiano, 2007