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 (
) 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.
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 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
Comments
Mod edit: image way too large.
http://i.imgur.com/A0Bx3CN.png
Me edit: The problem is fixed, you can submit now.
"If it is possible for her to do this, output −1."
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?
Sorry it was a typo, and it is the cheapest option with a larger cost.
When you say if it is possible, I think you mean the opposite.
Relevant: In re Sample Input 2, CAN IT BE?