UTS Open '15 #5 - Distribution Channel

View as PDF

Submit solution


Points: 17 (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 second cheapest way to connect her stores.

Mrs. Evans hopes to open N (1 \le N \le 50\,000) stores and there are M (1 \le M \le 100\,000) possible connections between her stores. The i^\textbf{th} connection connects station a_i to station b_i with a cost of c_i. She can only choose N-1 connections.

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

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

Partial Marks

For 25% of the marks, you may assume that N \le 5\,000, M \le 10\,000.

For 50% of the marks, you may assume that N \le 10\,000, M \le 50\,000.

Input Format

The first line will contain N, and M. The i^\textbf{th} of the next M lines will contain a_i, b_i, and c_i, where (1 \leq a_i,b_i \leq N, a_i \neq b_i, 1 \leq c_i \leq 10\,000).

Output Format

A single line containing the 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 4:

  • 1 \to 2 with cost 1
  • 1 \to 3 with cost 3

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 11:

  • 1 \to 3 with cost 2
  • 3 \to 5 with cost 2
  • 3 \to 4 with cost 3
  • 2 \to 5 with cost 4

Comments


  • 2
    kobortor  commented on Aug. 10, 2015, 8:32 p.m. edit 2

    Mod edit: image way too large.

    http://i.imgur.com/A0Bx3CN.png

    Me edit: The problem is fixed, you can submit now.


  • 1
    sigkill  commented on Feb. 11, 2015, 4:59 p.m.

    "If it is possible for her to do this, output −1."


    • 1
      sigkill  commented on Feb. 11, 2015, 5:02 p.m.

      What if there are multiple ways of connecting the stores as cheaply as possible? Is the second-cheapest option then equal in cost to the cheapest option? Or do we find the cheapest option with a larger cost?


      • 1
        jeffreyxiao  commented on Feb. 11, 2015, 5:11 p.m.

        Sorry it was a typo, and it is the cheapest option with a larger cost.


  • 2
    bobhob314  commented on Feb. 11, 2015, 4:47 p.m.

    When you say if it is possible, I think you mean the opposite.


    • 0
      bobhob314  commented on Feb. 11, 2015, 4:48 p.m.

      Relevant: In re Sample Input 2, CAN IT BE?