Untitled

//#include<cstdio>
//#include<vector>
//#include<iostream>
//#include<stack>
//#include<algorithm>
//#include<queue>
//#include<math.h>
//#include<set>
//#define ll long long
//using namespace std;
//typedef pair<ll,ll> ii;
//ll d[1100];
//bool kt[1100];
//ll x[20][20];
//ll s[20];
//vector <ii> a[1100];
//
//ll k;
//ll F[18][140000];
//bool G[18][140000];
//ll n;
//
//
//void resetdata(){
//	for (int i=0; i<18; i++)
//		for (int j= 0; j < 140000; j++){
//			f[i][j] = 0;
//			G[i][j] = false;
//			
//		}
//	for (int i=0 ;i<1100; i++)
//	{
//		d[i] = 0;
//		kt[i] = false;
//	}
//}
//
//ll dijkstra(ll root,ll to)
//{
//	priority_queue < ii,vector <ii> ,greater<ii> > pq;
//	ll i,u,v;
//	ll du;
//	for(i=1;i<=n;i++) d[i]=10000000000000000ll;
//	d[root]=0ll;
//	pq.push(ii(0,root));
//	while(pq.size())
//	{
//		u=pq.top().second;
//		du=pq.top().first;
//		pq.pop();
//		if (du!=d[u]) continue;
//		for(i=0;v=a[u][i].first;i++)
//			if (d[v]>d[u]+a[u][i].second)
//			{
//				d[v]=d[u]+a[u][i].second;
//				pq.push(ii(d[v],v));
//			}
//	}
//	return d[to];
//}
//
//ll f(ll i,ll bit)
//{
//	ll res;
//	ll j;
//	if (bit==(1<<k)-1) if (i==k) return 0;
//	else return 10000000000000000ll;
//	if (G[i][bit]++) return F[i][bit];	
//	res=10000000000000000ll;
//	for(j=1;j<=k;j++)
//	if ((bit&(1<<(j-1)))==0) res=min(res,f(j,bit|(1<<(j-1)))+x[i][j]);
//	return F[i][bit]=res;
//}
//
//
//int main()
//{
//
//
//	int t;
//	cin>>t;
//	for (int i=0; i<t; i++){
//		ll m,i,u,v,w,res,j;
//		cin>>n>>m>>k;
//		k+=2;
//		
//		
//		
//		
//		for(i=2;i<k;i++) scanf("%lld",&s[i]);
//		s[1]=1;s[k]=1;
//		while(m--)
//		{
//			scanf("%lld%lld%lld",&u,&v,&w);
//			a[u].push_back(ii(v,w));
//		}
//		for(i=1;i<=n;i++) a[i].push_back(ii(0,0));
//		for(i=1;i<=k;i++)
//		for(j=1;j<=k;j++)
//		if (i!=j)
//			x[i][j]=dijkstra(s[i],s[j]);
//		if (f(1,1)>1000000000000000ll) cout<<-1;
//		else cout<<f(1,1)<<endl;	
//	}
//}