지뢰설치

지뢰 설치

이등병 종현이는 지뢰를 설치하는 임무를 부여받고 외나무다리에 K개의 지뢰를 설치하려 한다. 외나무다리의 각 지점은 1번부터 차례대로 N번까지 번호가 매겨져 있고, 최초 지뢰는 아무곳에나 설치하여도 상관없다. 다만 각 지점사이의 외나무다리의 상태나 주위 환경이 다르기 때문에 이동할때 드는 피로도가 출발지와 목적지에 따라 천차만별이다. a에서 b지점으로 이동할 때의 피로도와 b지점에서 a지점으로 이동할 때의 피로도가 다른 경우도 존재하며, 심지어 아예 이동이 불가능한 경로도 있다. 또한 외나무다리에 지뢰를 설치하기 때문에 한번 지뢰가 설치된 곳을 지나서 이동하는 것은 불가하다. 종현이가 느끼는 피로도를 최소로 하여 K개의 지뢰를 설치하는 방법을 찾는 프로그램을 작성하자. 단, K개의 지뢰를 설치하는 방법이 존재하지 않는다면 -1을 출력하도록 한다.

 

[제한사항]

1. 종현이는 지뢰가 놓여지지 않은 지점에 도착하면 무조건 그곳에 지뢰를 설치한다.

2. 한 지점에는 한 개의 지뢰만 설치할 수 있다.

3. 최초 지뢰를 놓는 지점은 1 ~ N 중 아무곳이나 가능하며, 이 때 느끼는 피로도는 없다.

 

[입력]

최초 테스트케이스의 개수 T가 주어지며, 다음 줄부터 T개의 테스트 케이스가 주어진다. 각 테스트 케이스마다 첫 번째 줄엔 지점의 수 N과 설치해야 할 폭탄의 수 K가 공백을 두고 차례대로 주어진다.(1 ≤ K ≤ N ≤ 80) 그 다음줄엔 이동할 수 있는 두 지점의 수 M이 주어지고, 그 다음 M줄에 걸쳐 시작점, 도착점, 피로도가 순서대로 주어진다. (1 ≤ M ≤ min(N*(N-1),3000))

(1 ≤ 시작점, 도착점 ≤ N, 1 ≤ 피로도 ≤ 1000)

 

[출력]

각각의 테스트 케이스에 대하여 #x (x는 테스트 케이스 번호, 1부터 시작)을 출력하고 공백을 하나 둔 다음, 종현이가 K개의 지뢰를 설치할 때 느끼는 최소의 피로도를 출력한다.

 

[입출력예제]

입력

3

5 3

4

4 2 3

2 4 3

4 5 3

5 2 2

3 3

4

1 2 542

1 3 729

3 1 4

2 3 378

3 2

10

2 3 293

3 1 978

3 1 859

1 2 236

1 2 368

2 1 423

1 3 919

2 1 226

1 3 149

1 2 574

 

출력

#1 5

#2 546

#3 149

 

1

2

3

4

5

3

3

3

2

[Case 1] N=5, K=3인 경우

 위 예제의 경우 2 → 4 → 5 로 이동하며 6의 피로도를 느끼며 3개의 지뢰를 설치할 수 있다.

4 → 5 → 2 로 가는경우 5 → 2로 이동할 때 4를 지나야 하므로 이동이 불가능하다.