timchutrinhvainraduondidfs

#include <iostream>

using namespace std;

int n;
int a[1002][1002];
int w[1002];
int hascycle;
int vs[1003];
int parent[1003];
int di[1003];
int ans;

void memm()
{
	for (int i=0; i<=1000; i++)
	{
		w[1002] = 0;
	    for (int j=0; j<=1000; j++)
		a[i][j] = 0;
	}
}


void induongdi(int dau, int cuoi) {
	int cur = dau;
	

	while (true) {
		cout << cur << "-->" << di[cur] << endl;
		cur = di[cur];
		if (cur == cuoi) {
			break;
		}
	}
	cout << cuoi << "-->" << di[cuoi] << endl;
	
}


int breakcycle(int dau, int cuoi)
{
	int v1 = dau;
	int v2 = cuoi;
	int minn = a[v1][v2];
	int cur = cuoi;

	while (parent[cur] != -1)
	{
		if (a[cur][parent[cur]] < minn)
		{
			minn = a[cur][parent[cur]];
			v1 = cur;
			v2 = parent[cur];
		}
		cur = parent[cur];
	}
	a[v1][v2] = 0;
	a[v2][v1] = 0;
	return minn;
}


void resetvs(){
	for (int i = 1; i<=1000; i++)
	{
		vs[i] = 0;
	    parent[i] = -1;
		di[i] = -1;
	}
}


void DFS(int start, int i, int pre)
{
	//cout << pre << " " << i << endl;
	vs[i] = 1;
	parent[i] = pre;
	if (hascycle == 1) return;
	for (int j = 0; j<n; j++)
	if (j != pre)
	{
		if (hascycle == 1) return;
		if (a[i][j] != 0 && vs[j] == 0)
		{
			di[i] = j;
			DFS(start, j,i);
		} else if (a[i][j] != 0 && vs[j] == 1 && j == start)
		{
			ans += breakcycle(start, i);
			hascycle = 1;
			di[i] = start;
			induongdi(start, i);
			return;
		}
	}
	//vs[i] = 0;
}


int main()
{
	//freopen("Text.txt","r",stdin);
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{

		memm();
		cin >> n;
		for (int k = 0; k < n; k++){
			int id, ntl;
			cin >> id;
			cin >> w[id];
			cin >> ntl;

			for (int i = 1; i <=ntl; i++)
			{
				int v;
				cin >> v;
				a[id][v] = 1;
				a[v][id] = 1;
			}
		}

		for (int i = 0; i<n; i++)
			for (int j=0; j<n; j++)
				if (a[i][j] == 1)
					a[i][j] = w[i] + w[j];
        
		
		ans = 0;
		/*
		for (int i = 0; i < n; i++) {
			resetvs();
			hascycle = 0;
			DFS(i, i, -1);
			// neu co chu trinh, sau khi da xoa di roi, tim tiep tu do xem con chu trinh ko
			if (hascycle == 1) {
				i--;
			}
			
		}
		*/
		resetvs();
		DFS(0, 0, -1);

		cout << "Case #"<< tc <<  endl << ans << endl;
	}

	return 0;
}