1081 - Building roads
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