## UTS Open '15 #5 - Distribution Channel (Hard)

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types
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
Distribution channels are often very confusing.

After acquiring enough funding and finally finishing the development for her product, Mrs. Evans wants to release it to the local market. However, the Canadian Competition Act prevents her from choosing the cheapest way to connect her stores.

In order to spend the least amount of money and abide to the Canadian Competition Act, she must find the strictly second cheapest way to connect her stores.

Mrs. Evans hopes to open () stores and there are () possible connections between her stores. The connection connects station to station with a cost of . She can only choose connections.

If it is impossible for her to do this, output .

N.B. The time limit is rather strict for certain slow languages like Python and Java. C++ is recommended for this question.

Note: extra test cases were added courtesy of zxyl to break incorrect solutions.

#### Partial Marks

For 25% of the marks, you may assume that , .

For 50% of the marks, you may assume that , .

#### Input Format

The first line will contain , and . The of the next lines will contain , , and , where ().

#### Output Format

A single line containing the strictly second cheapest way to connect her stores.

#### Sample Input 1

3 3
1 2 1
2 3 2
3 1 3

#### Sample Output 1

4

#### Explanation

Mrs. Evans chooses the following connections for a total cost of :

• with cost
• with cost

#### Sample Input 2

5 10
2 3 5
1 5 5
1 2 3
1 3 2
5 3 2
4 3 3
4 5 9
4 2 10
5 2 4
4 1 9

#### Sample Output 2

11

#### Explanation

Mrs. Evans chooses the following connections for a total cost of :

• with cost
• with cost
• with cost
• with cost