#include <cstdio>#include <map>#include <string>#include <algorithm>using namespace std;const int MAXN = 2010;const int MAXM = 50010;map<string, int> hash;int cnt;struct EE { int u, v, w;}ee[MAXM];int tot;bool cmp(const EE &cmp1, const EE &cmp2){ return cmp1.w < cmp2.w;}int fa[MAXN];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]);}int main(){ int cn, cns; char str1[110], str2[110]; int cost; string tmp1, tmp2; scanf("%d", &cns); for (cn = 0; cn < cns; cn++) { int n, m; scanf("%d%d", &n, &m); cnt = 0; tot = 0; hash.clear(); for (int i = 0; i < m; i++) { scanf("%s%s%d", str1, str2, &cost); tmp1 = str1; tmp2 = str2; if (hash.find(tmp1) == hash.end()) { hash[tmp1] = cnt++; } if (hash.find(tmp2) == hash.end()) { hash[tmp2] = cnt++; } ee[tot].u = hash[tmp1]; ee[tot].v = hash[tmp2]; ee[tot].w = cost; tot++; } sort(ee, ee + tot, cmp); for (int i = 0; i < cnt; i++) fa[i] = i; int fx, fy; int ans = 0; for (int i = 0; i < tot; i++) { fx = find(ee[i].u); fy = find(ee[i].v); if (fx != fy) { fa[fx] = fy; ans += ee[i].w; } } printf("%dn", ans); } return 0;}
