Crypto Trading

All submissions for this problem are available.
AMRExchange is the latest cryptocurrency exchange that has become very popular among cryptocurrency traders.
On AMRExchange, there are N cryptocurrencies  let us denote the i^{th} currency by C_{i}. M pairs of these cryptocurrencies are tradable  one unit of currency C_{x} can be converted to one unit of currency C_{y} with risk C_{xy}.
Mr. X, an avid cryptocurrency collector, wants to start with 1 unit of any of the N cryptocurrencies and perform a sequence of trades. He wants to do it in such a way that for each of the N cryptocurrencies, there was at least one point during the trading sequence during which he held one unit of that cryptocurrency.
The overall risk of the sequence of trades is the maximum risk in the sequence of trades. Minimize the overall risk with which Mr. X can achieve this. Print "Impossible" if no such sequence of trades is possible.
Input
 The first line contains a single integer T  the total number of testcases.

Each testcase is of the following format:
 First line contains 2 spaceseparated integers  N and M. N denotes the number of cryptocurrencies, M denotes the number of tradable ordered cryptocurrency pairs.
 M lines follow. Each line contains 3 spaceseparated positive integers  C_{x}, C_{y} and C_{xy}. This line denotes that one unit of currency C_{x} can be converted into one unit of currency C_{y} with risk C_{xy}.
Output
 For each testcase, print the minimum overall risk with which Mr. X can own at least one unit of each cryptocurrency at some point in time.
 If it is not possible for Mr. X to achieve this, then print “Impossible”.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N, M ≤ 10^{5}
 1 ≤ C_{x}, C_{y} ≤ N
 1 ≤ C_{xy} ≤ 10^{9}
Example
Input 2 3 6 1 2 1 2 3 3 3 1 3 1 3 1 3 2 1 3 2 5 4 3 1 2 1 2 3 1 2 4 1 Output 1 Impossible
Explanation
Testcase 1: Mr. X can start with cryptocurrency C_{1} and follow the following sequence to minimize overall risk:
 Convert C_{1} to C_{3} with risk 1.
 Convert C_{3} to C_{2} with risk 1.
The overall risk would be 1.
Testcase 2: There are a total of 6 sequences of trades are possible, and none of them satisfy our property. We list them here:
Starting with C_{1}:
 C_{1} > C_{2} > C_{3}
 C_{1} > C_{2} > C_{4}
In the first sequence, Mr. X won't be able to own C_{4} because units of C_{3} cannot be converted to units of C_{4}. Similarly, in the second sequence, Mr. X won't be able to own C_{3} because units of C_{4} cannot be converted to units of C_{3}.
Starting with C_{2}:
 C_{2} > C_{3}
 C_{2} > C_{4}
Starting with C_{3}:
 C_{3} (cannot be converted to any other cryptocurrency)
Starting with C_{4}:
 C_{4} (cannot be converted to any other cryptocurrency)
Hence, there is no possible sequence using which Mr. X can own one unit of all cryptocurrencies at some point in time.
Author:  wittyceaser 
Tags  wittyceaser 
Date Added:  23122017 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 