Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 623
Solved: 100
Description
Jone was gaven S dollars and told to build some roads between N (2 <= N <= 500) farms (numbered from 1 to N).
The roads should satisfy the following rules:
1), There should be at least one path between any two farms.
2), The cost of all the roads dose not exceed S .
3), The maximum difference of the cost between any two roads should be as low as possible.
4), If there are multi ways to build the roads, you should choose cheapest one.
Input
There are multi test cases.
For each test case: In the first line, there are three integers: N(2 <= N <= 500), M(2 <= M <= 2000) and S.
In the next M lines, there are three positive integers: Fi, Ti and Si; specifies that Jone can build a road between farm Fi and farm Ti with a cost of Si.
Output
For each test case, output two numbers in a line. The first one is the maximum diffence of the cost between any two roads, the second one is the total cost of all the roads. The two numbers should be separated by just one space.
If Jone cannot build the roads described above, just output "impossible".
sample input
4 3 1000
1 2 1
2 3 999
3 4 1
3 3 100
1 2 23
2 3 1000
1 3 43
sample output
impossible
20 66
hint
source
Wu sl
Submit