stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.215801494062049x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.146431475512803x):
#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;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define Would

#define you

#define please





int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);



	

	//順列生成なんてライブラリがあるんですね版

	int N, M, R;

	cin >> N >> M >> R;

	int r[8];

	rep(i, R) cin >> r[i];

	sort(r, r + R);



	int D[201][201];

	rep1(i, 200) {

		rep1(ii, 200) {

			D[i][ii] = 30000000;

		}

	}



	rep(i, M) {

		int A, B, C;

		cin >> A >> B >> C;

		D[A][B] = C;

		D[B][A] = C;

	}



	rep1(k, N) {

		rep1(i, N) {

			rep1(j, N) {

				if (D[i][j] > D[i][k] + D[k][j]) D[i][j] = D[i][k] + D[k][j];

			}

		}

	}



	int kumiawase = 1;

	rep1(i, R) kumiawase *= i;



	int saishou = 1e9;

	rep(i, kumiawase) {

		int goukei = 0;

		rep(i, R - 1) goukei += D[r[i]][r[i + 1]];

		saishou = min(saishou, goukei);



		next_permutation(r, r + R);

	}



	co(saishou);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1522310669400113x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



int N, M, R;

int D[201][201];

int r[8];

int kotae;

int ima;

bool v[8];

void sagasu(int n, int prev) {

	if (n == R) kotae = min(kotae, ima);

	else {

		rep(i, R) {

			if (!v[i]) {

				v[i] = 1;

				if (prev >= 0) ima += D[r[prev]][r[i]];

				sagasu(n + 1, i);

				if (prev >= 0) ima -= D[r[prev]][r[i]];

				v[i] = 0;

			}

		}

	}

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	cin >> N >> M >> R;

	rep(i, R) cin >> r[i];



	rep1(i, N) rep1(j, N) D[i][j] = 1e9;

	rep(i, M) {

		int a, b, c;

		cin >> a >> b >> c;

		D[a][b] = c;

		D[b][a] = c;

	}

	rep1(k, N) rep1(i, N) rep1(j, N) {

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

	}



	kotae = 1e9;

	sagasu(0, -1);



	co(kotae);



	Would you please return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define Would

#define you

#define please





int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);



	

	//順列生成なんてライブラリがあるんですね版

	int N, M, R;

	cin >> N >> M >> R;

	int r[8];

	rep(i, R) cin >> r[i];

	sort(r, r + R);



	int D[201][201];

	rep1(i, 200) {

		rep1(ii, 200) {

			D[i][ii] = 30000000;

		}

	}



	rep(i, M) {

		int A, B, C;

		cin >> A >> B >> C;

		D[A][B] = C;

		D[B][A] = C;

	}



	rep1(k, N) {

		rep1(i, N) {

			rep1(j, N) {

				if (D[i][j] > D[i][k] + D[k][j]) D[i][j] = D[i][k] + D[k][j];

			}

		}

	}



	int kumiawase = 1;

	rep1(i, R) kumiawase *= i;



	int saishou = 1e9;

	rep(i, kumiawase) {

		int goukei = 0;

		rep(i, R - 1) goukei += D[r[i]][r[i + 1]];

		saishou = min(saishou, goukei);



		next_permutation(r, r + R);

	}



	co(saishou);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.149373725118524x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll; 

#define PT pair<int, int>

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



int N, M, R;

int E[201][201];

int D[8][201];

int r[8];

int kotae;

int ima;

bool v[8];

void sagasu(int n, int prev) {

	if (n == R) kotae = min(kotae, ima);

	else {

		rep(i, R) {

			if (!v[i]) {

				v[i] = 1;

				if (prev >= 0) ima += D[prev][r[i]];

				sagasu(n + 1, i);

				if (prev >= 0) ima -= D[prev][r[i]];

				v[i] = 0;

			}

		}

	}

}



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);





	cin >> N >> M >> R;

	rep(i, R) cin >> r[i];



	rep1(i, N) {

		rep1(j, N) E[i][j] = 1e9;

		E[i][i] = 0;

	}

	rep(i, M) {

		int a, b, c;

		cin >> a >> b >> c;

		E[a][b] = c;

		E[b][a] = c;

	}



	rep(i, R) rep1(j, N) D[i][j] = 1e9;

	rep(i, R) D[i][r[i]] = 0;



	priority_queue<PT, vector<PT>, greater<PT>> que;



	rep(k, R) {

		que.push(mp(0, r[k]));

		while (que.size()) {

			PT p = que.top();

			que.pop();

			int i = p.second;

			if (D[k][i] != p.first) continue;

			rep1(j, N) {

				ll d = D[k][i] + E[i][j];

				if (D[k][j] > d) {

					D[k][j] = d;

					que.push(mp(d, j));

				}

			}

		}

	}



	kotae = 1e9;

	sagasu(0, -1);



	co(kotae);



	Would you please return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3284196892065812x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.101141814992511x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.3183340598513253x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.2768094931442928x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.1512882597307172x):
#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;

}
// Slower C++ solution:
#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;

    

    

}


// Faster C++ solution for the same problem (measured speedup: 2.2944872059551447x):
#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;

}