1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 10 #define typec int11 using namespace std;12 13 const int V = 1005;14 const typec inf = 0xffff;15 int vis[V];16 typec lowc[V];17 int Map[V][V];18 19 typec prim (typec cost[][V], int n) {20     int i, j, p;21     typec minc, res = 0;22     memset(vis, 0, sizeof(vis));23     vis[0] = 1;24     for (i = 1; i < n; ++ i) lowc[i] = cost[0][i];25     for (i = 1; i < n; ++ i) {26         minc = inf; p = -1;27         for (j = 0 ; j < n; ++ j) {28             if (0 == vis[j] && minc > lowc[j]) {29                 minc = lowc[j]; p = j;30             }31         }32         if (inf == minc) return -1;33         res += minc; vis[p] = 1;34         for (j = 0 ; j < n; ++ j) {35             if (0 == vis[j] && lowc[j] > cost[p][j]) {36                 lowc[j] = cost[p][j];37             }38         }39     }40     return res;41 }42 43 int main () {44     int n, road_n;45     int cur = 0;46     while (cin >> n >> road_n) {47         /*if (cur ++ != 0) {48             cout << endl;49         }*/50         for (int i = 0 ; i < n; ++ i) {51             for (int j = 0 ; j < n; ++ j) {52                 if (i == j) Map[i][j] = 0;53                 else {54                     Map[i][j] = inf;55                 }56             }57         }58 59         for (int i = 0 ; i < road_n; ++ i) {60             int x, y, c;61             scanf("%d%d%d", &x, &y, &c);62             if (x == y) {63                 continue;64             }65             Map[x][y] = Map[y][x] = min(Map[x][y], c);66         }67 68         int ans = prim (Map, n);69 70         if (ans == -1) {71             cout << "impossible" << endl << endl;72         } else {73             cout << ans << endl << endl;74         }75     }76     return 0;77 }