#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 998244353;
#define VQ vector<priority_queue<pair<ll,vector<int>>>>
#define VQQ vector<vector<pair<ll,vector<int>>>>

int V, E, T;
int deri[10500];
vector<pair<int, int>> G[405];
VVI kyori(401, VI(401, INF));
VVI prever(401, VI(401, -1));
vector<vector<vector<int>>> keiro(401, vector<vector<int>>(401));
int road[401][401];
int store_max = 500;
VI ans;
ll point = 0;
VI tmp;
ll sonshitu = 50000000LL;
VI F(401);


//string fileName1 = "C:/Users/r/Desktop/toolkitA/scripts/sa11.in";
//std::ifstream ci(fileName1);
//string fileName = "syuturyoku.txt";
//std::ofstream cou(fileName);

void nyuuryoku() {

cin >> V >> E;
REP(i, E) {
int u, v, d;
cin >> u >> v >> d;
u--; v--;
G[u].push_back({ v,d });
G[v].push_back({ u,d });
road[u][v] = d;
road[v][u] = d;
}
REP(i, V)cin >> F[i];
cin >> T;

REP(i, V) {
sort(ALL(G[i]));
}
}

void dijkstra(int s) {
int vis[405];
REP(i, V) vis[i] = 0;

min_priority_queue<pair<ll, int>> que;

kyori[s][s] = 0;
que.push({ 0, s });

while (!que.empty()) {
auto q = que.top();
que.pop();

int cst = q.first;
int cu = q.second;

if (vis[cu]) continue;
vis[cu] = 1;

fore(p, G[cu]) {
int cst2 = cst + p.second;
int to = p.first;

if (chmin(kyori[s][to], cst2)) {
que.push({ kyori[s][to], to });
prever[s][to] = cu;
}
}
}
}

void get_path(int s, int t) {
int tt = t;
vector<int> path;
while (1) {
t = prever[s][t];
if (s == t)break;
path.push_back(t);
}

reverse(path.begin(), path.end());

path.push_back(tt);

for (int i : path) {
keiro[s][tt] = path;
}
}

void saitankeiro() {
REP(i, V) {
dijkstra(i);
}


REP(i, V)REP(j, V) {
if (i == j)continue;
get_path(i, j);
}
}

//ansを更新する
void update(ll a) {
if (a > point) {
point = a;
ans = tmp;
}
}

//tmpに解答をいれて計算する
void calc() {

ll cur = 0;
ll cnt = 0;
int now = 0;
int dst = 0;

VVI store(401);
VVI car(401);
VVI kara(401);
VI kar;

REP(i, T) {
if (deri[i] != 0)store[deri[i]].push_back(i);
if (tmp[i] == -1)continue;
if (now == 0 && dst == 0) {
REP(j, 401) {
for (int k : store[j]) {
car[j].push_back(k);
}
}
store = kara;
}

if (now == tmp[i]) {
dst--;
}
else {
dst = kyori[now][tmp[i]] - 1;
now = tmp[i];
}
if (dst == 0) {
for (int j : car[now]) {
cur -= (ll)((i - j + 1)*(i - j + 1));
}
cnt += car[now].size();
car[now] = kar;

}

}
update(cnt * 100000000LL + cur);
}

//荷物が多いところ（max-kk個以内ならOK）に行く
vector<int> h(int k, int kk) {
VB store(405, false);
VB car(405, false);
int now = 0;
VI an;
VI st(405, 0);
VI ca(405, 0);
REP(_, T) {

store[deri[_]] = true;
store[0] = false;

st[deri[_]]++;
st[0] = 0;

int c = 0;
REP(i, V)c += st[i];
if (c > k && now != 0) {
while (now != 0) {
int ti = kyori[now][0];
for (int j : keiro[now][0]) {
REP(k, kyori[now][j]) {
an.push_back(j);
}
car[now] = false;
ca[now] = 0;
now = j;
}
REP(j, ti - 1) {
_++;
if (deri[_] != 0) {
store[deri[_]] = true;
st[deri[_]]++;
}
}
}
continue;
}
if (now == 0) {
REP(i, V) {
if (store[i]) car[i] = true;
store[i] = false;
ca[i] += st[i];
st[i] = 0;
}
}

bool ch = false;
REP(i, V) {
if (car[i]) ch = true;
}

if (ch) {

int ma = 0;
REP(i, V) {
ma = max(ma, ca[i]);
}

vector<pair<int, int>> v;

REP(i, V) {
if (ca[i] >= max(1, ma - kk)) {
v.push_back({ kyori[now][i],i });
}
}
sort(ALL(v));
int to = keiro[now][v[0].second][0];
bool b = false;
REP(i, kyori[now][to]) {

an.push_back(to);

if (!b)b = true;
else {
_++;
if (deri[_] != 0) {
store[deri[_]] = true;
st[deri[_]]++;
}
}
}
now = to;
car[to] = false;
ca[to] = 0;
}
else if (now == 0)an.push_back(-1);
else {
int ti = kyori[now][0];
for (int j : keiro[now][0]) {
REP(k, kyori[now][j]) {
an.push_back(j);
}
car[now] = false;
ca[now] = 0;
now = j;
}
REP(j, ti - 1) {
_++;
if (deri[_] != 0) {
store[deri[_]] = true;
st[deri[_]]++;
}
}
}
}
while (an.size() < 10005)an.push_back(-1);

return an;
}

//荷物が多いところ（max-kk個以内ならOK）
//帰っていく際に隣接した点にkkk個以上あるなら経由する
vector<int> hh(int k, int kk, int kkk) {

VB store(405, false);
VB car(405, false);

int now = 0;
VI an;
VI st(405, 0);
VI ca(405, 0);
REP(_, T) {
store[deri[_]] = true;
store[0] = false;

st[deri[_]]++;
st[0] = 0;

int c = 0;
REP(i, V)c += st[i];
if (c > k && now != 0) {
int ti = kyori[now][keiro[now][0][0]];
int to = keiro[now][0][0];
vector<pair<int, int>> vv;
for (pair<int, int> i : G[now]) {
if (ca[i.first] > kkk) {
vv.push_back({ -ca[i.first],i.first });
}
}
if (vv.size()) {
sort(ALL(vv));
to = vv[0].second;
ti = kyori[now][to];
}
for (int i : keiro[now][to]) {
REP(j, kyori[now][i]) {
an.push_back(i);
}
now = i;
ca[i] = 0;
car[i] = false;
}
car[to] = false;
ca[to] = 0;
now = to;
REP(j, ti - 1) {
_++;
if (deri[_] != 0) {
store[deri[_]] = true;
st[deri[_]]++;
}
}
continue;
}
if (now == 0) {
REP(i, V) {
if (store[i]) car[i] = true;
store[i] = false;
ca[i] += st[i];
st[i] = 0;
}
}

bool ch = false;
FOR(i, 1, V) {
if (car[i]) ch = true;
}

if (ch) {

int ma = 0;
REP(i, V) {
ma = max(ma, ca[i]);
}

vector<pair<int, int>> v;

REP(i, V) {
if (ca[i] >= max(1, ma - kk)) {
v.push_back({ kyori[now][i],i });
}
}
sort(ALL(v));
int to = keiro[now][v[0].second][0];
bool b = false;
REP(i, kyori[now][to]) {

an.push_back(to);


if (!b)b = true;
else {
_++;
if (deri[_] != 0) {
store[deri[_]] = true;
st[deri[_]]++;
}
}
}
now = to;
car[to] = false;
ca[to] = 0;
}
else if (now == 0) {
an.push_back(-1);
}
else {
int ti = kyori[now][0];
for (int j : keiro[now][0]) {
REP(k_, kyori[now][j]) {
an.push_back(j);
}
car[now] = false;
ca[now] = 0;
now = j;
}
REP(j, ti - 1) {
_++;
if (deri[_] != 0) {
store[deri[_]] = true;
st[deri[_]]++;
}
}
}
}
while (an.size() < 10005)an.push_back(-1);

return an;
}


int nn, id, dst;
string verdict;

void beam_search6(int beam,int time_h) {

VVI store(405);
VVI car(405);
VI kar;
VVI kara(405);
int now = 0;
VI an;
VI st(405, 0);
VI ca(405, 0);
bool check_9500 = true;

REP(i, T) {
cin >> nn;
if (nn) {
cin >> id >> dst;
dst--;
deri[i] = dst;
}
cin >> nn;
REP(j, nn) {
cin >> id;
}
if (deri[i] != 0) {
st[deri[i]]++;
store[deri[i]].push_back(i);
}
if (now == 0) {
REP(j, V) {
for (int k : store[j])car[j].push_back(k);
ca[j] += st[j];
st[j] = 0;
}
store = kara;
}
bool check_car = false;
REP(j, V)if (ca[j] > 0)check_car = true;
if (!check_car) {
cout << -1 << endl;
cin >> verdict;
if (verdict == "NG")return;
cin >> nn;
REP(j, nn)cin >> id;
continue;
}
int cnt = 0;
VQQ q(time_h + 610);
q[0].push_back({ 0, { 0 } });
ll cur = 0;
ll time_cur = 1000000;
VI as;
//cout << i << ' ' << i + time_h << endl;
if ((i + time_h) < 9500) {
REP(j, min(T - i, time_h + 600)) {
int cu = 0;
while (!q[j].empty()) {
if (cu >= beam)break;
cu++;
ll point1 = q[j].back().first;
VI v = q[j].back().second;
VI vv = v;
ll point3 = point1;
q[j].pop_back();
if (vv[vv.size() - 1] != 0) {
ll aa = j + kyori[v[v.size() - 1]][0];
VB check_ca(401, false);
REP(k, V)if (ca[k] > 0)check_ca[k] = true;
for (int k : vv)check_ca[k] = false;
for (int k : keiro[v.back()][0]) {
vv.push_back(k);
if (check_ca[k]) {
for (int l : car[k]) {
point3 += 100000000LL;
point3 -= (ll)((l - i - j - kyori[v.back()][k])*(l - i - j - kyori[v.back()][k]));
}
}
}
if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
if (aa < time_h) {
if (point3 > cur) {
cur = point3;
time_cur = aa;
as = vv;
}
}
else {
if (point3*time_cur > aa*cur) {
cur = point3;
as = vv;
time_cur = aa;
}
}
}
}

VB check_c(401, false);
REP(k, V)if (ca[k] != 0)check_c[k] = true;
for (int k : v)check_c[k] = false;
REP(k, V) {
if (check_c[k]) {
ll point2 = point1;
for (int l : car[k])point2 += 100000000 - (ll)((i + j + kyori[k][v[v.size() - 1]] - l)*(i + j + kyori[k][v[v.size() - 1]] - l));
VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 600) {
int ti1 = j + kyori[k][v.back()];
q[ti1].push_back({ point2,vvv });
if (q[ti1].size() > beam) {
sort(ALL(q[ti1]));
reverse(ALL(q[ti1]));
q[ti1].pop_back();
}
}
}
}
}
}
}
else {
if (check_9500) {
check_9500 = false;
REP(j, 9500 - i) {
int cu = 0;
while (!q[j].empty()) {
if (cu >= beam)break;
cu++;
ll point1 = q[j].back().first;
VI v = q[j].back().second;
VI vv = v;
ll point3 = point1;
q[j].pop_back();
if (vv[vv.size() - 1] != 0) {
ll aa = j + kyori[v[v.size() - 1]][0];
VB check_ca(401, false);
REP(k, V)if (ca[k] > 0)check_ca[k] = true;
for (int k : vv)check_ca[k] = false;
for (int k : keiro[v.back()][0]) {
vv.push_back(k);
if (check_ca[k]) {
for (int l : car[k]) {
point3 += 100000000LL;
point3 -= (ll)((l - i - j - kyori[v.back()][k])*(l - i - j - kyori[v.back()][k]));
}
}
}
if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
if (aa < time_h) {
if (point3 > cur) {
cur = point3;
time_cur = aa;
as = vv;
}
}
else {
if (point3*time_cur > aa*cur) {
cur = point3;
as = vv;
time_cur = aa;
}
}
}
}


VB check_c(401, false);
REP(k, V)if (ca[k] != 0)check_c[k] = true;
for (int k : v)check_c[k] = false;
REP(k, V) {
if (check_c[k]) {
ll point2 = point1;
for (int l : car[k])point2 += 100000000 - (ll)((i + j + kyori[k][v[v.size() - 1]] - l)*(i + j + kyori[k][v[v.size() - 1]] - l));
VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 600) {
int ti1 = j + kyori[k][v.back()];
q[ti1].push_back({ point2,vvv });
if (q[ti1].size() > beam) {
sort(ALL(q[ti1]));
reverse(ALL(q[ti1]));
q[ti1].pop_back();
}
}
}
}
}
}
}
else {
REP(j, T - i) {
int cu = 0;
while (!q[j].empty()) {
if (cu >= beam)break;
cu++;
ll point1 = q[j].back().first;
VI v = q[j].back().second;
VI vv = v;
ll point3 = point1;
q[j].pop_back();
if (cur < point3) {
cur = point3;
as = v;
}
VB check_c(401, false);
REP(k, V)if (ca[k] != 0)check_c[k] = true;
for (int k : v)check_c[k] = false;
REP(k, V) {
if (check_c[k]) {
ll point2 = point1;
for (int l : car[k])point2 += 100000000LL - (ll)((i + j + kyori[k][v.back()] - l)*(i + j + kyori[k][v.back()] - l));
VI vvv = v;
vvv.push_back(k);
if (i + j + kyori[k][v.back()] < T) {
int ti1 = j + kyori[k][v.back()];
q[ti1].push_back({ point2,vvv });
if (q[ti1].size() > beam) {
sort(ALL(q[ti1]));
reverse(ALL(q[ti1]));
q[ti1].pop_back();
}
}
}
}
}
}
}
}

if (cur == 0) {
cout << -1 << endl;
cin >> verdict;
if (verdict == "NG")return;
cin >> nn;
REP(j, nn)cin >> id;
continue;
}

int cntr = 0;
as.erase(as.begin());

VI abc;

for (int j : as) {
for (int k : keiro[now][j]) {
REP(l, kyori[now][k]) {
abc.push_back(k);
cntr++;
}
now = k;
ca[k] = 0;
car[k] = kar;
}
}

bool use = true;

REP(j, abc.size()) {
if (!use) {
i++;
cin >> nn;
if (nn) {
cin >> id >> dst;
dst--;
deri[i] = dst;
if (deri[i] != 0) {
st[deri[i]]++;
store[deri[i]].push_back(i);
}
}
cin >> nn;
REP(k, nn)cin >> id;
}
if (use)use = false;
cout << abc[j] + 1 << endl;
cin >> verdict;
if (verdict == "NG")return;
cin >> nn;
REP(k, nn)cin >> id;
}
}

}



//2s
void solve() {
for (int i = 100; i <= 300; i += 10) {
FOR(j, 3, 7) {
tmp = h(i, j);
calc();
}
}
for (int i = 100; i <= 300; i += 10) {
FOR(j, 3, 5) {
REP(k, 2) {
tmp = hh(i, j, k);
calc();
}
}
}
}

int main() {

nyuuryoku();

saitankeiro();



//solve();

beam_search6(12, 25);
return 0;
}

Measured memory_bytes: 20956