stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <queue>

#include <string>

#include <cstdio>

#include <cmath>

#include <sstream>

#include <algorithm>



using namespace std;



vector<vector<int> > d;

const int INF = 100000000;



void warshall_floyd(int n) {

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n; j++) {

			for (int k = 0; k < n; k++) {

				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);

			}

		}

	}

}



int main() {

	int n, m, r;

	cin >> n >> m >> r;

	vector<int> rr;

	for (int i = 0; i < r; i++) {

		int t;

		cin >> t;

		rr.push_back(t);

	}



	d.resize(n+1);

	for (int i = 0; i < n+1; i++) {

		d[i].resize(n+1);

		for (int j = 0; j < n+1; j++) {

			d[i][j] = INF;

			d[i][i] = 0;

		}

	}

	for (int i = 0; i < m; i++) {

		int from, to, cost;

		cin >> from >> to >> cost;

		d[from][to] = cost;

		d[to][from] = cost;

	}

	warshall_floyd(n+1);

	sort(rr.begin(), rr.end());

	int min = INF+1;

	do{

		int total = 0;

		for (int i = 1; i < r; i++) {

			total += d[rr[i - 1]][rr[i]];

		}

		if (min > total) min = total;

	} while (next_permutation(rr.begin(), rr.end()));

	cout << min << endl;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <string.h>

#include <algorithm>



using namespace std;



#define N 220

#define INF 0x3f3f3f3f



int d[N][N];

int a[N];



void floyd(int n) {

    for (int k = 1; k <= n; ++k) {

        for (int i = 1; i <= n; ++i) {

            for (int j = 1; j <= n; ++j) {

                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

            }

        }

    }

}



int main() {

    int n, m, r;

    while (scanf("%d%d%d", &n, &m, &r) != EOF) {

        for (int i = 0; i < r; ++i) scanf("%d", &a[i]); sort(a, a + r);

        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) d[i][j] = (i == j ? 0 : INF);

        for (int i = 0; i < m; ++i) {

            int u, v, w; scanf("%d%d%d", &u, &v, &w); d[u][v] = d[v][u] = w;

        }

        int res = INF;

        floyd(n);

        do {

            int tmp = 0;

            for (int i = 1; i < n; ++i) tmp += d[a[i - 1]][a[i]];

            res = min(res, tmp);

        } while (next_permutation(a, a + r));

        printf("%d\n", res);

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;



long long mat[207][207];

int ord[10];

long long ans = 1e16;

long long inf = 1e16;

int main(){

	int n,m,r;

	int a,b,c;

	

	cin >> n >> m >> r;

	

	for(int i = 1;i<=n;i++){

		for(int j = 1;j<=n;j++){

			if(i==j){

				mat[i][j] = 0;

				mat[j][i] = 0;

			}

			else{

				mat[i][j] = inf;

				mat[j][i] = inf;

			}

		}

	}

	

	for(int i = 0;i < r;i++){

		cin >> ord[i];

	}

	

	while(m--){

		cin >> a >> b >> c;

		mat[a][b] = c;

		mat[b][a] = c;

	}

	

	for(int k = 1;k<=n;k++){

		for(int i = 1;i<=n;i++){

			for(int j = 1;j<=n;j++){

				if(mat[i][j]>mat[i][k]+mat[k][j]){

					mat[i][j] = mat[i][k]+mat[k][j];

				}

			}

		}

	}

	sort(ord,ord+r);

	while(next_permutation(ord,ord+r)){

		long long sum = 0;

		for(int i = 1;i < r;i++){

			sum+=mat[ord[i]][ord[i-1]];

		}

		ans = min(sum,ans);

	}

	cout << ans;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <string.h>

#include <algorithm>



using namespace std;



#define N 220

#define INF 0x3f3f3f3f



int d[N][N];

int a[N];



void floyd(int n) {

    for (int k = 1; k <= n; ++k) {

        for (int i = 1; i <= n; ++i) {

            for (int j = 1; j <= n; ++j) {

                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

            }

        }

    }

}



int main() {

    int n, m, r;

    while (scanf("%d%d%d", &n, &m, &r) != EOF) {

        for (int i = 0; i < r; ++i) scanf("%d", &a[i]); sort(a, a + r);

        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) d[i][j] = (i == j ? 0 : INF);

        for (int i = 0; i < m; ++i) {

            int u, v, w; scanf("%d%d%d", &u, &v, &w); d[u][v] = d[v][u] = w;

        }

        int res = INF;

        floyd(n);

        do {

            int tmp = 0;

            for (int i = 1; i < n; ++i) tmp += d[a[i - 1]][a[i]];

            res = min(res, tmp);

        } while (next_permutation(a, a + r));

        printf("%d\n", res);

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



int main() {

  int n, m, R;

  cin >> n >> m >> R;



  vector<int> r(R);

  for (int i = 0; i < R; i++) {

    cin >> r[i];

    r[i]--;

  }

  sort(r.begin(), r.end());



  ll d[210][210];

  fill(d[0], d[210], 1LL << 30);

  for (int i = 0; i < n; i++) {

    d[i][i] = 0;

  }



  for (int i = 0; i < m; i++) {

    int a, b, c;

    cin >> a >> b >> c;

    a--, b--;

    d[a][b] = d[b][a] = c;

  }

  for (int k = 0; k < n; k++) {

    for (int i = 0; i < n; i++) {

      for (int j = 0; j < n; j++) {

        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

      }

    }

  }



  ll ans = 1LL << 30;

  do {

    ll sub = 0;

    for (int i = 0; i + 1 < R; i++) {

      sub += d[r[i]][r[i + 1]];

    }

    ans = min(ans, sub);

  } while (next_permutation(r.begin(), r.end()));

  cout << ans << endl;



  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;

using pii = pair<int, int>;



const int INF = 1 << 30;

int main() {

  cin.tie(0);

  ios_base::sync_with_stdio(false);

  cout << fixed << setprecision(10);

  

  int N, M, R;

  cin >> N >> M >> R;



  vector<int> r(R);

  for (int i = 0; i < R; i++) {

    cin >> r[i];

    r[i]--;

  }

  sort(r.begin(), r.end());



  int dis[210][210];

  fill((int*)dis, (int*)(dis + N), INF);

  for (int i = 0; i < N; i++) dis[i][i] = 0;

  for (int i = 0; i < M; i++) {

    int A, B, C;

    cin >> A >> B >> C;

    A--, B--;

    dis[A][B] = dis[B][A] = C;

  }

  for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {

    if (dis[i][k] == INF || dis[k][j] == INF) continue;

    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

  }

  int ans = INF;

  do {

    int sub = 0;

    for (int i = 0; i + 1 < R; i++) {

      sub += dis[r[i]][r[i + 1]];

    }

    ans = min(ans, sub);

  } while (next_permutation(r.begin(), r.end()));

  cout << ans << endl;



  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <map>

#include <vector>



using namespace std;



int N,M,R;

int r[8];

int d[205][205];

int ans;

int per[8];

int used[8];



void warshall_floyd(){

	int i,j,k;



	for(k=1;k<=N;k++){

		for(i=1;i<=N;i++){

			for(j=1;j<=N;j++){

				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

			}

		}

	}



}



void dfs(int depth){



	int i;



	if(depth==R){





		int cost=0;



		for(i=0;i<R-1;i++){

			int from=r[per[i]-1];

			int to=r[per[i+1]-1];

			cost+=d[from][to];

		}



		if(ans>cost){ans=cost;}



		return ;

	}



	for(i=0;i<R;i++){



	if(used[i]==0){

		per[depth]=i+1;

		used[i]=1;

		dfs(depth+1);

		used[i]=0;

		}

	}

}



int main(){



	scanf("%d %d %d",&N,&M,&R);



	int i,j;



	for(i=1;i<=N;i++){

		for(j=1;j<=N;j++){

			if(i==j){d[i][j]=0;}

			else{d[i][j]=1<<25;}

		}

	}





	for(i=0;i<R;i++){

		scanf(" %d",&r[i]);

	}

	for(i=0;i<M;i++){

		int A,B,C;

		scanf("%d %d %d",&A,&B,&C);

		d[A][B]=C;

		d[B][A]=C;

	}



	warshall_floyd();



	ans=1<<30;



	dfs(0);



	printf("%d\n",ans);



	return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>



int N,M,R;

int r[8];

int d[205][205];

int ans;

int per[8];

int used[8];



int min(int a,int b){

	if(a<b){return a;}

	else{return b;}

}



void warshall_floyd(){

	int i,j,k;



	for(k=1;k<=N;k++){

		for(i=1;i<=N;i++){

			for(j=1;j<=N;j++){

				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

			}

		}

	}



}



void dfs(int depth){



	int i;



	if(depth==R){





		int cost=0;



		for(i=0;i<R-1;i++){

			int from=r[per[i]-1];

			int to=r[per[i+1]-1];

			cost+=d[from][to];

		}



		if(ans>cost){ans=cost;}



		return ;

	}



	for(i=0;i<R;i++){



	if(used[i]==0){

		per[depth]=i+1;

		used[i]=1;

		dfs(depth+1);

		used[i]=0;

		}

	}

}



int main(){



	scanf("%d %d %d",&N,&M,&R);



	int i,j;



	for(i=1;i<=N;i++){

		for(j=1;j<=N;j++){

			if(i==j){d[i][j]=0;}

			else{d[i][j]=1<<25;}

		}

	}





	for(i=0;i<R;i++){

		scanf(" %d",&r[i]);

	}

	for(i=0;i<M;i++){

		int A,B,C;

		scanf("%d %d %d",&A,&B,&C);

		d[A][B]=C;

		d[B][A]=C;

	}



	warshall_floyd();



	ans=1<<30;



	dfs(0);



	printf("%d\n",ans);



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



#define MAX_V 205

#define INF 1e9



long long int d[MAX_V][MAX_V]={0}; // d[u][v]は辺e=(u,v)のコスト(存在しない場合はINF、ただしd[i][i]=0とする)

int V;       // 頂点数

int r[9];



void warshall_floyd() {

  for (int k = 1; k <= V; k++)

    for (int i = 1; i <= V; i++)

      for (int j = 1; j <= V; j++)

        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

}



int main(){

    int n, m, R;



    cin >> n >> m >> R;

    for(int i=0;i<R;++i){

        cin >> r[i];

    }

    for(int i=0;i<MAX_V;++i){

        for(int j=0;j<MAX_V;++j){

            if(i!=j)d[i][j] = INF;

        }

    }

    for(int i=0;i<m;++i){

        int a,b,c;

        cin >> a >> b >> c;

        d[a][b] = c;

        d[b][a] = c;

    }

    V = n;

    warshall_floyd();

    long long int mini = LLONG_MAX;

    sort(r,r+R);

    do{

        long long int sum = 0;

        for(int i=0;i<R-1;++i){

            sum += d[r[i]][r[i+1]];

        }

        if(mini > sum)mini = sum;

    }while(next_permutation(r,r+R));



    cout << mini << endl;



    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



using i64 = long long int;



i64 cost[203][203] = {0};



int main(){

    int n, m, r;

    cin >> n >> m >> r;

    vector<int> v;

    for(int i=0;i<r;++i){

        int tmp;

        cin >> tmp;

        v.push_back(tmp);

    }



    for(int i=1;i<=n;++i)

        for(int j=1;j<=n;++j)

            if(i != j) cost[i][j] = LLONG_MAX;



    for(int i=0;i<m;++i){

        i64 a, b, c;

        cin >> a >> b >> c;

        cost[a][b] = c;

        cost[b][a] = c;

    }



    for(int k=1;k<=n;++k){

        for(int i=1;i<=n;++i){

            for(int j=1;j<=n;++j){

                if(cost[i][k] == LLONG_MAX || cost[k][j] == LLONG_MAX)continue;

                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);

            }

        }

    }



    sort(v.begin(), v.end());

    i64 ans = LLONG_MAX;

    do{

        int curr = v[0];

        i64 tmp = 0;

        for(int i=1;i<r;++i){

            tmp += cost[curr][v[i]];

            curr = v[i];

        }

        ans = min(tmp, ans);

    }while(next_permutation(v.begin(), v.end()));



    cout << ans << endl;



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

const int INF = 100000000;

const int N_MAX = 200;



typedef long long ll;



int N;

int M;

int R;





ll d[300][300];



vector<int> r;







int main()

{

	for(int i = 0;i < 300;i++)

	{

		for(int j = 0;j < 300;j++)

		{

			d[i][j] = INF;

		}

	}

	int a,b,c,ri;

	cin >> N >> M >> R;

	for(int i = 0;i < R;i++)

	{

		cin >> ri;

		r.push_back(ri);	

	}

	for(int i = 0;i < M;i++)

	{

		cin >> a >> b >> c;

		d[a][b] = c;

		d[b][a] = c;

	}

	

for(int k = 1;k <= N;k++)

			{

	for(int i = 1;i <= N;i++)

	{

		for(int j = 1;j <= N;j++)

		{

			

				d[i][j] = min(d[i][j],d[i][k] + d[k][j]);

}

		}

	}

	

	ll min_ = 100000000000LL;



	sort(r.begin(),r.end());

	

	do

	{

		ll sum = 0;

		for(int i = 0;i < r.size() - 1;i++)

		{

			sum += d[r[i]][r[i+1]];

		}

		min_ = min(min_,sum);

	} while(next_permutation(r.begin(),r.end()));

	cout << min_ << endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#include <string.h>

#include <cmath>



using namespace std;

typedef long long i64;

typedef long double ld;

typedef pair<i64,i64> P;

#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))



int n;

int m;

int r;



i64 dist[210][210];



int q[10];



int main()

{

	for(int i =0;i < 210;i++) for(int j = 0;j < 210;j++)

		dist[i][j] = 1e18;

	cin >> n >> m >> r;

	for(int i = 0;i < r;i++)

		cin >> q[i];

	for(int i = 0;i < m;i++)

	{

		int a,b;

		i64 c;

		cin >> a >> b >> c;

		dist[a][b] = c;

		dist[b][a] = c;

	}



	for(int k = 1;k <= n;k++)

	{

		for(int i = 1;i <= n;i++)

		{

			for(int j = 1;j <= n;j++)

			{

				dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);

			}

		}

	}



	i64 result = 1e18;



	sort(q , q + r);

	do

	{

		i64 sum = 0;

		for(int i = 1;i < r;i++)

		{

			sum += dist[q[i - 1]][q[i]];

		}

		result = min(result , sum);

	} while(next_permutation(q,q + r));





	cout << result << endl;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <algorithm>

#include <functional>

#include <vector>

#include <utility>

#include <cstring>

#include <iomanip>

#include <numeric>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int INF = 1<<30;

const int MOD = 1e9 + 7;

const int dy[] = {1, 0, -1, 0};

const int dx[] = {0, 1, 0, -1};

const int MAX_N = 210;

int main()

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n, m, r; cin >> n >> m >> r;

    vector<int> v(r);

    for(int i = 0; i < r; i++) { cin >> v[i]; v[i]--; }

    sort(v.begin(), v.end());

    ll dist[MAX_N][MAX_N];

    for(int i = 0; i < MAX_N; i++)

    {

        for(int j = 0; j < MAX_N; j++) dist[i][j] = INF;

        dist[i][i] = 0;

    }

    for(int i = 0; i < m; i++)

    {

        int a, b, c; cin >> a >> b >> c;

        a--, b--;

        dist[a][b] = c;

        dist[b][a] = c;

    }

    for(int k = 0; k < n; k++)

        for(int i = 0; i < n; i++)

            for(int j = 0; j < n; j++)

                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    ll ans = INF;

    do

    {

        ll total = 0;

        for(int i = 1; i < r; i++) total += dist[v[i]][v[i - 1]];

        ans = min(ans, total);

    }

    while(next_permutation(v.begin(), v.end()));

    cout << ans << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <algorithm>

#include <functional>

#include <vector>

#include <utility>

#include <cstring>

#include <iomanip>

#include <numeric>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int INF = 1<<29;

const int MOD = 1e9 + 7;

const int dy[] = {1, 0, -1, 0};

const int dx[] = {0, 1, 0, -1};

const int MAX_N = 210;

int main()

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n, m, r; cin >> n >> m >> r;

    vector<int> v(r);

    for(int i = 0; i < r; i++) { cin >> v[i]; v[i]--; }

    sort(v.begin(), v.end());

    int dist[MAX_N][MAX_N];

    for(int i = 0; i < MAX_N; i++)

    {

        for(int j = 0; j < MAX_N; j++) dist[i][j] = INF;

        dist[i][i] = 0;

    }

    for(int i = 0; i < m; i++)

    {

        int a, b, c; cin >> a >> b >> c;

        a--, b--;

        dist[a][b] = c;

        dist[b][a] = c;

    }

    for(int k = 0; k < n; k++)

        for(int i = 0; i < n; i++)

            for(int j = 0; j < n; j++)

                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int ans = INF;

    do

    {

        int total = 0;

        for(int i = 1; i < r; i++) total += dist[v[i]][v[i - 1]];

        ans = min(ans, total);

    }

    while(next_permutation(v.begin(), v.end()));

    cout << ans << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <map>

using namespace std;



struct UF{

    int par[200000];

    int rank[200000];

    

    void init(int n){

        for(int i=0;i<n;i++){

            par[i]=i;

            rank[i]=0;

        }

    }

    

    int find(int x){

        if(par[x]==x)return x;

        return par[x]=find(par[x]);

    }

    

    void unite(int x, int y){

        x=find(x);

        y=find(y);

        if(x!=y){

            if(rank[x]<rank[y]){

                par[x]=y;

            }else{

                par[y]=x;

                if(rank[x]==rank[y])rank[x]++;

            }

        }

    }

    

    bool same(int x, int y){

        return find(x)==find(y);

    }

};



int main(void){

    int h,w;

    long long t=0;

    string s[404];

    UF u;

    map<int,long long> a,b;

    cin>>h>>w;

    u.init(160008);

    for(int i=0;i<h;i++){

        cin>>s[i];

    }

    for(int i=0;i<h;i++){

        for(int j=0;j<w;j++){

            if(j<w-1){

                if(s[i][j]!=s[i][j+1]){

                    u.unite(i*400+j,i*400+j+1);

                }

            }

            if(i<h-1){

                if(s[i][j]!=s[i+1][j]){

                    u.unite(i*400+j,(i+1)*400+j);

                }

            }

        }

    }

    for(int i=0;i<h;i++){

        for(int j=0;j<w;j++){

            int m=i*400+j,l;

            l=u.find(m);

            if(s[i][j]=='#'){

                a[l]++;

            }else{

                b[l]++;

            }

        }

    }

    

    for(auto x=a.begin();x!=a.end();x++){

        int k=x->first;

        t+=a[k]*b[k];

    }

    

    cout<<t<<endl;

    

    

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

using namespace std;



typedef pair<long long, long long> P;



int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int h,w;

string s[400];

bool b[400][400];



P f(int y, int x){

    long long c=0,d=0;

    b[y][x]=true;

    if(s[y][x]=='#'){

        c++;

    }else{

        d++;

    }

    for(int i=0;i<4;i++){

        int nx=x+dx[i],ny=y+dy[i];

        if(ny>=0&&ny<h&&nx>=0&&nx<w){

            if(!b[ny][nx]&&s[y][x]!=s[ny][nx]){

                P p=f(ny,nx);

                c+=p.first;

                d+=p.second;

            }

        }

    }

    return P(c,d);

}



int main(void){

    long long t=0;

    cin>>h>>w;

    for(int i=0;i<h;i++){

        cin>>s[i];

        for(int j=0;j<w;j++){

            b[i][j]=false;

        }

    }

    

    for(int i=0;i<h;i++){

        for(int j=0;j<w;j++){

            if(!b[i][j]){

                P p=f(i, j);

                t+=p.first*p.second;

            }

        }

    }

    

    cout<<t<<endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

const int N=1e5+10;

typedef long long LL;



vector<int> v[N];

int a[N];

int b[N];



int dp[1<<15];



int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=m;i++)

    {

        cin>>a[i];

        int c;

        cin>>c;

        for(int j=1;j<=c;j++)   

        {

            int u;

            cin>>u;

            u--;

            b[i]|=(1<<u);

        }

        //cout<<b[i]<<endl;

    }





    for(int i=1;i<=m;i++)

    {

        int u=b[i];



        for(int j=0;j<(1<<n);j++)

        {

            if(j==0||dp[j])

            {

                if(dp[u|j])

                {

                    dp[u|j]=min(dp[u|j],dp[j]+a[i]);

                }

                else

                {

                    dp[u|j]=dp[j]+a[i];

                }

            }

        }

    }



    if(dp[(1<<n)-1])

        cout<<dp[(1<<n)-1]<<endl;

    else

        cout<<-1<<endl;

    



    

    //system("pause");

}

// Optimized solution to the same problem (faster):
#include<cstring>

#include<algorithm>

#include<cstdio>

#define N 10005

#define INF 0x3f3f3f3f

using namespace std;

long long int d[N];

long long int a[1005];

int v[15];

int s[10005];

int b[1005];

int c[15];

int n;

int m;

int tar;

long long int ans=INF;

int main(){

scanf("%d%d",&n,&m);

//for(int i=1;i<=n;i++){

//l[i][0]=0;

//}

memset(d,0x3f,sizeof(d));

memset(v,0,sizeof(v));

memset(s,0,sizeof(s));



for(int i=1;i<=m;i++){

int x,y;

scanf("%lld%d",&a[i],&y);

int st=0;

for(int j=1;j<=y;j++){

scanf("%d",&c[j]);

v[c[j]]++;

st+=(1<<(c[j]-1));

}

b[i]=st;

}

tar=0;

for(int i=1;i<=n;i++){

tar+=(1<<(i-1));

if(v[i]==0){

printf("-1");

return 0;

}

}

d[0]=0;

for(int i=0;i<=tar;i++){

for(int j=1;j<=m;j++){

if(d[i|b[j]]>d[i]+a[j]){

d[i|b[j]]=d[i]+a[j];

}

}



}

printf("%lld",d[tar]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



#ifdef NeverBeRed

#include "debug.h"

#else

#define debug(...) 9715

#endif

typedef long long ll;

typedef long double ld;

typedef complex<ll> point;

#define F first

#define S second



struct info

{

	int c, m;

};



int main()

{

	#ifdef TurnRed

		//freopen("a.in", "r", stdin);

		//freopen("a.out", "w", stdout);

	#endif



	ios_base::sync_with_stdio(0), cin.tie(0);



	int n, m;

	cin >> n >> m;

	vector<info> a;

	for (int k; m--; )

	{

		a.push_back({ 0, 0 });

		cin >> a.back().c >> k;

		for (int i = 0, x; i < k; ++i)

		{

			cin >> x;

			a.back().m |= 1<<(x-1);

		}

	}



	vector<int> dp(1<<n, 1e9);

	dp[0] = 0;

	for (int i = 0; i < 1<<n; ++i)

		for (auto j : a)

			dp[i | j.m] = min(dp[i | j.m], dp[i] + j.c);



	int ans = dp[(1<<n)-1];

	if (ans >= 1e9) ans = -1;

	cout << ans << "\n";



	return 0;

}


// Optimized solution to the same problem (faster):
#include<cstring>

#include<algorithm>

#include<cstdio>

#define N 10005

#define INF 0x3f3f3f3f

using namespace std;

long long int d[N];

long long int a[1005];

int v[15];

int s[10005];

int b[1005];

int c[15];

int n;

int m;

int tar;

long long int ans=INF;

int main(){

scanf("%d%d",&n,&m);

//for(int i=1;i<=n;i++){

//l[i][0]=0;

//}

memset(d,0x3f,sizeof(d));

memset(v,0,sizeof(v));

memset(s,0,sizeof(s));



for(int i=1;i<=m;i++){

int x,y;

scanf("%lld%d",&a[i],&y);

int st=0;

for(int j=1;j<=y;j++){

scanf("%d",&c[j]);

v[c[j]]++;

st+=(1<<(c[j]-1));

}

b[i]=st;

}

tar=0;

for(int i=1;i<=n;i++){

tar+=(1<<(i-1));

if(v[i]==0){

printf("-1");

return 0;

}

}

d[0]=0;

for(int i=0;i<=tar;i++){

for(int j=1;j<=m;j++){

if(d[i|b[j]]>d[i]+a[j]){

d[i|b[j]]=d[i]+a[j];

}

}



}

printf("%lld",d[tar]);

}

// Fastest known solution for this problem: