인터넷 설치

컴퓨터는 1번부터 N번까지 번호가 붙어 있다. 처음에는 어떤 컴퓨터도 서로 연결되어 있지 않지만, 연결할 수 있는 케이블 후보 P개가 주어진다. 각 후보는 두 컴퓨터와 설치 비용을 가진다.

1번 컴퓨터는 이미 인터넷 서버에 직접 연결되어 있다. 목표는 설치한 케이블들을 통해 1번 컴퓨터와 N번 컴퓨터가 서로 연결되도록 만드는 것이다. 다른 컴퓨터들이 인터넷에 연결되는지는 상관없다.

총 K개의 케이블은 무료로 설치할 수 있다. 무료 케이블을 제외한 나머지 설치한 케이블들에 대해서는, 그중 가장 비싼 케이블의 비용만 지불하면 된다. 목표를 달성하기 위해 지불해야 하는 최소 금액을 구하라.

첫째 줄에 컴퓨터 수 N(1 ≤ N ≤ 1,000), 연결 가능한 케이블 수 P(1 ≤ P ≤ 10,000), 무료로 설치할 수 있는 케이블 수 K(0 ≤ K < N)가 주어진다.

다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 설치 비용이 주어진다. 비용은 1 이상 1,000,000 이하이다.

1번 컴퓨터와 N번 컴퓨터를 연결하기 위해 지불해야 하는 최소 금액을 출력한다. 연결할 수 없다면 -1을 출력한다.

1-3, 3-2, 2-5 경로를 사용하면 케이블 비용은 각각 4, 3, 9이다.

무료로 설치할 수 있는 케이블이 1개 있으므로 비용 9인 케이블을 무료로 처리할 수 있다. 남은 케이블 중 가장 비싼 비용은 4이므로 지불 금액은 4가 된다.