Woburn Challenge 2017-18 Finals Round - Senior Division

Problem 2: Cowmmunication Network

Great military strategists know that a battle occurs beyond just the front lines. To prepare for the the upcoming war against the Party of Extraterrestrial Gangsters, the cows and monkeys will need to have an impeccable communications network for relaying important military commands behind the scenes. To this end, chief scientist of the bovine army Guglielmoo Marcowni has developed a powerful new technology — the radio! While his radio technology is very impressive, it sometimes suffers from the issue of poor signals. To quantify the smoothness of a network, Marcowni has developed a measure of signal quality known as Communication Compatibility. A large Communication Compatibility score between radios suggests a great connection, a negative score suggests a very poor connection, and a score of zero suggests a so-so connection.

The cow-monkey army is made up of N (2 ≤ N ≤ 100,000) combat units, numbered from 1 to N. Each unit carries a single radio that can communicate with other radios via specific communication channels. In total, there are M (0 ≤ M ≤ 200,000) potential communication channels amongst all of the units. Implementing the i-th communication channel would allow units A_i and B_i (1 ≤ A_i, B_i ≤ N; A_i ≠ B_i) to radio each other directly, with a Communication Compatibility of C_i (−10⁶ ≤ C_i ≤ 10⁶). No two communication channels connect the same unordered pair of combat units.

Bo Vine and the Head-Monkey want to create a communication network out of one or more of the M potential communication channels. The network must be constructed such that every pair of combat units is able to communicate over the network, either directly or indirectly. If a combat unit i can communicate with both combat units j and k (either directly or indirectly), then combat units j and k are also considered able to communicate with each other indirectly.

Bo Vine and the Head-Monkey want to make their network as smooth as possible. Naturally, their choice will be based on the Communication Compability scores of the channels they choose to implement. To help them quantify the overall smoothness of the network, Marcowni has defined a benchmark known as the Cumulative Communication Compatibility (CCC) score. The CCC score of the network is defined to be the sum of the Communication Compatibilities of all communication channels that make up the network. Please help Marcowni determine the maximum possible CCC score that a valid network connecting all N combat units could have (note that this value may not fit into a 32-bit signed integer). Unfortunately, it's possible that no such valid network may exist, in which case you should report "Impossible" instead.

Subtasks

In test cases worth 3/13 of the points, N ≤ 10, M ≤ 10, and C_i < 0 for each i.
In test cases worth another 3/13 of the points, N ≤ 1000, M ≤ 2000, and C_i < 0 for each i.
In test cases worth another 6/13 of the points, N ≤ 1000, M ≤ 2000.

Input Format

The first line of input consists of two space-separated integers, N and M.
M lines follow, the i-th of which consists of three space-separated integers, A_i, B_i, and C_i, for i = 1..M.

Output Format

Output a single line consisting of either a single integer, the maximum possible CCC score of any valid network, or the string "Impossible" if no valid network exists.

Sample Input 1

4 5
1 2 -1
2 3 -5
3 4 -3
4 1 -2
4 2 -3

Sample Output 1

-6

Sample Input 2

5 4
1 2 5
2 3 2
3 1 -1
4 5 0

Sample Output 2

Impossible

Sample Explanation

In the first example, one possible optimal network is by implementing the first, third, and fourth communication channels. The CCC score of such a network is (−1) + (−3) + (−2) = −6.

In the second example, there is no way to allow any of the first three combat units to communicate with any of the last two units, so it is impossible to build a valid network.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: May 13, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)