习题8.4 畿通工程之最小生成树问题 (30 分)（最小生成树）

最小生成树算法应用

这里有详细的解答

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。

输入格式:

输入数据的第一行包含两个数值，分别为城镇的数量N（满足1<N≤1000）以及候选道路的数量M（不超过3N）。接下来的M行中，每一行均包含三个正整数，依次表示该道路所连接的两个城镇的编号（编号范围为1至N）以及该道路改建所需的预算成本。

输出格式:

计算实现畅通工程所需的最小成本。若输入数据无法确保工程畅通，则应输出“Impossible”。

输入样例1:

    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