Vacation in Graphopolis

We are in the year 7342 A.D., and our beloved tree city is experiencing significant economic growth. Many one-way roads have been constructed, turning it into what resembles a directed graph, hence it is now called Graphopolis. Each road connecting two vertices, u and v, has a weight w indicating the distance from vertex u to vertex v. Many tourists arrive in Graphopolis every year, and you, as a travel agency, want to capitalize on this opportunity. You want to organize the tourists into groups that you will guide through Graphopolis.

This year, exactly T tourists have arrived, who have been placed in the vertices from 1 to T. You want to divide these tourists into K groups. You are located at vertex T+1 and are responsible for communication for the travel agency. After the division into groups, each tourist must send a message to all the other members of their group. In order for a tourist located at vertex u to send a message to the tourist located at vertex v, they must follow the following procedure: Initially, they send the message via mail to you (i.e., vertex T+1), and then you, after signing it, send it back via mail to vertex v. However, since postage costs money and you want your customers to be satisfied, you need to properly divide the tourists into groups so that the total distance traveled to send all messages is minimized.

Input:

The first line of the input contains four positive integers N, K, T, and M: the number of vertices in Graphopolis, the number of groups into which you need to divide the tourists, the number of tourists, and the number of one-way roads in Graphopolis, respectively. The vertices are numbered from 1 to N. Then follow M lines (where 1 ~\le~ M ~\le~ 50000), each describing a road and containing three integers u, v, w: the road from vertex u to vertex v has distance w (where 0 ~\le~ w ~\le~ 10000). Assume that 1 ~\le~ K ~\le~ T ~<~ N and that there is always a way for a message to be sent from any tourist to you and vice versa.

Output:

You should print a single line containing one positive integer: the minimum total distance that will be traveled to send all messages in the optimal division of tourists into groups.

Note: All data is read from standard input and printed to standard output.

Constraints:

• For subtasks worth 15% of the total points, it holds:
  3 ~\le~ Ν ~\le~ 5000, K = 1
• For subtasks worth 30% of the total points, it holds:
  3 ~\le~ Ν ~\le~ 20, K = 2
• For subtasks worth 60% of the total points, it holds:
  3 ~\le~ Ν ~\le~ 250, 3 ~\le~ K ~\le~ 250
• For the full score, it holds:
  3 ~\le~ Ν ~\le~ 50000, 3~\le~ K ~\le~ 5000

Example Input:

5 2 4 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

Example Output:

13

Explanation of the Example:

The layout of Graphopolis is shown in the figure above. Tourists are located at vertices 1 through 4, and you are located at vertex 5. If you place tourists 1 and 2 in one group and tourists 3 and 4 in a second group, then the messages to be sent are:

• 1 ~\to~ 2: distance 1+1 = 2
• 2 ~\to~ 1: distance 1+2 = 3
• 3 ~\to~ 4: distance 2+4 = 6
• 4 ~\to~ 3: distance 0+2 = 2 thus the total distance is 2+3+6+2 = 13. This is the minimum possible.

Example of Input - Output

input

5 2 4 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

output

13