Minimum Walking Distance with Attraction Tickets

You are given a set of attractions connected by bidirectional roads. Each road has an associated walking distance. Starting at attraction 1, your goal is to visit all attractions with the minimum total walking distance. Additionally, you have ( m ) tickets, each of which allows you to skip walking along one road. This skip can be applied to any road that is part of your chosen path connecting all attractions. In other words, if you form a Minimum Spanning Tree (MST) of the graph, you may remove up to ( m ) of its most expensive edges, reducing the total walking distance accordingly.

Formally, let the MST of the graph have a total weight ( W ) and its edge weights be ( w_1, w_2, \ldots, w_{n-1} ). By using ( m ) tickets, you can subtract the sum of the ( m ) largest ( w_i ) values from ( W ). Your task is to calculate the minimum walking distance after optimally using the tickets.

inputFormat

The input is read from standard input (stdin). The first line contains two integers ( n ) and ( m ), where ( n ) is the number of attractions and ( m ) is the number of tickets available. The second line contains an integer ( k ), the number of roads. Each of the following ( k ) lines contains three integers ( u ), ( v ), and ( l ) representing a bidirectional road between attractions ( u ) and ( v ) with walking distance ( l ). It is guaranteed that the attractions are numbered from 1 to ( n ) and the graph is connected.

outputFormat

Output a single integer to standard output (stdout) — the minimum walking distance needed to visit all attractions after optimally using up to ( m ) tickets to bypass the most expensive roads in the MST of the graph.## sample

4 1
3
1 2 3
1 3 2
3 4 4

5