This is not an MST problem.

This is not an MST problem, because finally, we can have a graph with several connected components (not a tree). For example, if a city has a power station and the price to build a line to another city is too high we can just isolate this city. Such test:

4 2

1 4

0 1 1 7

1 0 5 2

1 5 0 2

7 2 2 0

The answer is 2.

We build line 1 <-> 2, 1 <-> 3. The total price is 2. It's not necessary to build any line to city 4.

I don't know, maybe there are no tests for such cases.

*Edited by author 09.10.2019 16:52*

Re: This is not an MST problem.

This is indeed an MST problem ; with the idea of a dummy vertex brought it. More about this problem can be read in the editorial of this problem - https://codeforces.com/problemset/problem/1245/D