```#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <cassert>
#include <string.h>

#include <time.h>
#include <random>
#include <iomanip>
using namespace std;

#define ll long long
#define N 10005
#define INF 10000000000

ll n, m;

vector<pair<ll,ll> > graph[N];
ll p[9];
ll dist[9][9];  //distance from each node to each other node. Node 0 denotes 0, otherwise node i denotes p[i-1]

ll curDist[N];

void dijkstra(ll u) {
curDist[u] = 0;

set<pair<ll,ll> > q; // {weight, node#}
for (ll i = 0; i < n; i++) {
if (i!=u) {
curDist[i] = INF;
}
q.insert({curDist[i], i});
}

while (!q.empty()) {
pair<ll,ll> cur = *q.begin();
q.erase(cur);
ll nodeDist = cur.first;
ll nodeI = cur.second;
for (ll i = 0; i < graph[nodeI].size(); i++) {
ll nb = graph[nodeI][i].first;
ll nbLen = graph[nodeI][i].second;

ll alt = nodeDist + nbLen;
if (alt < curDist[nb]) {
q.erase({curDist[nb],nb});
curDist[nb] = alt;
q.insert({curDist[nb],nb});
}
}
}
}

void solve() {
for (ll i = 0; i < N; i++)
graph[i].clear();

cin >> n >> m;
for (ll i = 0; i < m; i++) {
ll a, b, l;
cin >> a >> b >> l;
graph[a].push_back({b,l});
graph[b].push_back({a,l});
}
ll idols;
cin >> idols;
p[0] = 0;
for (ll i = 1; i <= idols; i++)
cin >> p[i];
ll a;
cin >> a;

//bfs from node 0 and each idol node
for (ll i = 0; i <= idols; i++) {
dijkstra(p[i]);
for (ll j = 0; j <= idols; j++) {
dist[i][j] = curDist[p[j]];
}
}

vector<ll> v;
for (ll i = 0; i < idols; i++)
v.push_back(i+1);

ll maxRes = 0;

do {
vector<ll> curV(idols+2);
curV[0] = 0;    curV[idols+1] = 0;
for (ll i = 0; i < idols; i++)
curV[i+1] = v[i];

ll curAir = a - dist[curV[0]][curV[1]];
ll res = 0;

for (ll i = 1; i < idols+1; i++) {
res++;
if (curAir >= dist[curV[i]][curV[idols+1]])
maxRes = max(res, maxRes);
else
break;
curAir -= dist[curV[i]][curV[i+1]];
}
} while (next_permutation(v.begin(), v.end()));

cout << maxRes << endl;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
ll t;
cin >> t;
for (ll i = 0; i < t; i++) {
solve();
}
}```