2049: 镖局运镖图

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：30 Solved：12

Description

镖局的运镖，就是运货（类似现在的物流）。镖局每到一个新地方开展业务，都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低，不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线，已知城市的地图，你需要选择一些道路进行疏通，以便镖局可以到达任意一个城市，要求花费的银子越少越好。

Input

第一行有两个数n和m，n表示有n个城市（编号从1到n），m表示有m条道路。接下来m行，每行形如“a b c”用来表示一条道路，意思是城市a到城市b连通且打点需要花费的银子数是c。

Output

若通过打点能抵达所有城市，则输出最少需要花费的银子总数。若不能抵达所有的城市则输出“impossible”。

Sample Input Copy 

3 3
1 2 1
1 3 2
2 3 4

Sample Output Copy 

3

HINT

2 < n,m <= 100000