농부 창호의 이웃인 농부 정택이는 자신의 K(2 ≤ K ≤ 40)마리의 소를 선택하여 릴레이 달리기 팀을 구성하려 한다.

이 달리기 시합은 정택이의 농장에서 치러지는데

이 농장에는 N(4 ≤ N ≤ 800)개의 필드(차례대로 1부터 N까지의 번호가 붙는다)와 M (1 ≤ M ≤ 4000)개의 길이 존재한다.

각 길은 두개의 필드를 연결하고 있으며, 각각의 길을 통해 필드 사이를 이동하는데 소요되는 시간은 각각 다르다.

또, 임의의 두 필드 사이에는 최대 한 개의 길이 있다.

첫 번째 소는 1번째 필드에서 경주를 시작하여 N번째 필드에서 경주를 마친다.

첫 번째 소가 경주를 마치면, 다음 소는 1번째 필드에서 다시 달리기 시작한다.

이런 식으로 K마리의 소가 모두 경주를 해야 한다.

이 경주에서, 두 마리의 소가 이동한 경로는 절대 같아서는 안 된다.

경로는 차례로 이동한 필드들의 번호의 수열을 뜻한다.

정택이의 소들이 모두 경주를 마치는 데 걸리는 시간을 최소로 하는 프로그램을 작성하라.

주어진 입력에 대해서, 항상 경주를 마칠 수 있는 방법이 존재한다.

모든 소들은 이미 방문한 필드를 여러 번 방문할 수 도 있다.

각각의 소들이 N번째 필드 에 도달하는 순간, 그 소의 경주는 종료된다.

소들의 계주 timer 1s memory 128MB

소들의 계주 1s 128MB