|
Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem description
The city of Konya has many historical and natural sites that are worth a visit. Travelling agencies organize different tours for visiting those places. One of those agencies promises its customers to visit exact number of those places in a tour. The tour starts from any place and ends at the same place. It is possible to pass over a place without performing a visit. The travelling agency wants to select the shortest possible tour. Make a program to calculate the length of the shortest such a tour. There is always a path between any two places in the city.
Input
The first line contains three integers N (1 <= N <= 20), M (3<= M <=8), and K representing total number of the places in the city; how many of them need to be visited; and number of the direct roads between the places respectively. There are no two direct roads between any two places. Each of the following K lines contains three positive integers A, B, and D. The A and B denote two different places, and D (1 <= D <= 100) denotes the length of the direct road connecting them.
Output
The output has a single integer representing the length of the shortest tour.
Example
| stdin |
stdout |
5 4 7
1 5 3
5 4 2
4 3 3
3 1 10
1 4 15
2 3 5
2 1 3
|
16 |
Для отправки решений необходимо выполнить вход.
|