#include<bits/stdc++.h>
using namespace std;
#define TRACE 1
#define tcout TRACE && cout
#define int long long
#define endl '\n'
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N=1e3+100,M=2e6+10,INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int s;
int a[N],b[N],c[N];
int read()
{
	int res=0;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		res=res*2+(c=='1'?1:0);
	}
	return res;
}
int idx;
int h[N];
int e[M];
int wt[M];
int ne[M];
void add_edge(int u, int v, int w)
{
	idx++;
	e[idx]=v;
	wt[idx]=w;
	ne[idx]=h[u];
	h[u]=idx;
	
}
int d[N];
int vis[N];
int spfa(int s)
{
	queue<int>q;
	for(int i=1;i<(1<<n);i++)
	{
		d[i]=INF;
		vis[i]=0;
	}
	d[s]=0;
	q.push(s);
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=h[u];i;i=ne[i])
		{
			int v=e[i];
			int w=wt[i];
			if(d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				if(vis[v]==0)
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	if(d[0]==INF)
	{
		return -1;
	}
	return d[0];
}
void solve()
{
	idx=0;
	memset(h,0,sizeof(h));
	cin>>n>>m;
	s=read();
	for(int i=1;i<=m;i++)
	{
		cin>>c[i];
		a[i]=read();
		b[i]=read();
	}
	for(int i=0;i<(1<<n);i++)
	{
		int u=i;
		for(int j=1;j<=m;j++)
		{
			int v=u&(~a[j])|b[j];
			int w=c[j];
			add_edge(u,v,w);
		}
	}
	cout<<spfa(s)<<'\n';
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	cout<<'\n';
	system("pause");
	return 0;
}

莫名全输出0。┭┮﹏┭┮