[BOJ] 12784 : 인하니카 공화국

#include <cstdio>
#include <vector>
using namespace std;

struct edg { int idx, dst; };
vector<edg> gph[1001];

int dfs(int prv, int now, int dst) {
	int ret = 0;
	for (edg nxt : gph[now]) if (prv != nxt.idx)
		ret += dfs(now, nxt.idx, nxt.dst);
	if (!ret) ret = dst;
	return ret < dst ? ret : dst;
}

int main() {
	int tc, n, m;
	for (scanf("%d", &tc); tc--;) {
		scanf("%d %d", &n, &m);
		for (int i = 0, u, v, w; i < m; i++) {
			scanf("%d %d %d", &u, &v, &w);
			gph[u].push_back({ v,w });
			gph[v].push_back({ u,w });
		}
		printf("%d\n", m ? dfs(0, 1, 1e9) : 0);
		for (int i = 0; i <= n; i++) gph[i].resize(0);
	}

	return 0;
}