-->
当前位置:首页 > 题库

PROGRAMMING:The lowest cost construction of unimpeded project

Luz5年前 (2021-05-10)题库466
Through the investigation of urban traffic conditions in a certain area, the statistical data of the existing expressways between cities and towns are obtained, and the goal of "smooth engineering" is put forward: to realize the rapid traffic between any two cities and towns in the whole area (but there is not necessarily a direct connection between the expressways, as long as they can reach each other indirectly through the expressways). Now we get the statistical table of urban roads, which lists the cost of several roads that may be built into expressways, and seeks the minimum cost of smooth engineering.
###Input format:
The first line of input gives the number of towns $$n $$($$1 < n / Le 1000 $$) and the number of candidate roads $$m / Le 3N $$; In the following $$M $$lines, each line gives three positive integers, which are the number of the two towns directly connected by the road (from 1 to $$n $) and the estimated cost of the road reconstruction.
###Output format:
Output the minimum cost required for smooth engineering. If the input data is not enough to ensure smooth, the output "impossible".
###Input sample 1:
```in
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
```
###Output sample 1:
```out
twelve
```
###Input sample 2:
```
5 4
1 2 1
2 3 2
3 1 3
4 5 4
```
###Output sample 2:
```
Impossible
```






answer:If there is no answer, please comment