OCC '19 G5 - King kobortor's Infrastructure

View as PDF

Submit solution

Points: 17
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

King kobortor, the ruler of HillThorn, feels the infrastructure in his country is too old. So, he wants to upgrade the infrastructure. HillThorn is a country with N cities (1 \le N \le 1\,000), and M (1 \le M \le 5\,000) bidirectional roads, where the i^{th} road connects cities u_i and v_i (1 \le u_i, v_i \le N) with weight w_i (1 \le w_i \le 1\,000). There may be multiple roads between cities u_i and v_i. Suppose that the country is connected. The cost of bad infrastructure is the weight of the largest road in the country. King kobortor has the superpower to upgrade the roads around a city to weight 0. However, using this superpower on k cities will cost 10 * k^2. Please help King kobortor to find out the minimum sum of costs. The sum of costs includes the cost of the largest road and the cost of using the superpower.

Input Specification

The first line contains two integers, N and M, the number of cities and the number of roads.

Each of the following M lines contains three integers, u v and w, a road connecting cities u and v with weight w.

Output Specification

One integer, the minimum sum of costs.

Sample Input 1

2 1
1 2 58

Sample Output 1


Sample Input 2

6 10
5 6 901
2 6 173
3 5 610
3 5 598
1 5 142
1 2 699
1 5 904
2 4 633
3 6 6
1 4 573

Sample Output 2


Explanation to Sample Output

In the 1^{st} sample case, King kobortor can apply the superpower on city 1 or 2 to get a total cost of 10.

In the 2^{nd} sample case, King kobortor can apply the superpower on cities 1 2 and 5 with a cost of 90 and then the largest road is between cities 3 and 6 with a cost of 6. Thus the total cost is 96.


For all test cases, 1 \le N \le 1\,000, 1 \le M \le 5\,000, and 1 \le w \le 1\,000.

Subtask Points Additional constraints
1 13 N \le 15
2 17 w \le 10
3 23 w \le 90
4 47 No additional constraints.


There are no comments at the moment.