All Tracks Algorithms Graphs Biconnected Components Problem

A peaceful separation
Tag(s):

Medium-Hard

Problem
Editorial
Analytics

Trystland is a country with n cities and m weighted undirected roads such that there is atleast one possible path between any two cities. It is guaranteed that there is atmost one road between any two cities. However, due a to a difference in opinion on how the national number of the country should be decided, the people in Trystland have decided to separate into two countries. You have been assigned the duty to carry out the separation process in a peaceful way.

You have to divide the cities of Trystland into two countries A and B such that there is no path from any city in country A to any city in country B. However, there should still be atleast one path between any two cities of country A and any two cities of country B using the orignal roads of Trystland. The only operation that you are allowed to perform is to remove any one road of Trystland and then assign each city to either country A or country B.

Country A wants their national number to be weight of minimum spanning tree of all roads in country A whereas Country B wants their national number to be the weight of maximum spanning tree of all roads in country B. To make sure that the separation process is peaceful, you have to remove the road in such a way that the absolute difference between the national numbers of the two countries is as low as possible.

Input
The first line of the input contains two space separated integers n and m, the number of cities in Trystland and the number of roads in Trystland respectively. The next m line contains three space separated integers u,v and w in each line where w is the weight of the road between u and v respectively.

Output
If there's no way to carry out the separation satisfying the required conditions of the process print -1 otherwise print the minimum absolute difference between the national numbers of the two countries in a single line.

Constraints

  • $$3 \le n \le 10^5 $$
  • $$2 \le m \le 10^5 $$
  • $$1 \le w \le 10^6 $$
SAMPLE INPUT
3 2
1 2 3
2 3 4
SAMPLE OUTPUT
3
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIT Delhi

Challenge Name

ICPC de Tryst

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications