#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;



//string fileName1 = "C:/Users/r/Desktop/toolkitA/scripts/sa11.in";
//std::ifstream ci(fileName1);
//string fileName = "C:/Users/r/Desktop/toolkitA/scripts/output.out";
//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;
}
cin >> T;

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

int cnt = 0;

REP(i, T) {
int n;
cin >> n;
if (n) {
int id, dst;
cnt++;
cin >> id >> dst;
dst--;
deri[i] = dst;
}
}
}

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);
}



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) {
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) {
an.push_back(-1);
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) {
an.push_back(-1);
continue;
}

int cntr = 0;
as.erase(as.begin());
for (int j : as) {
for (int k : keiro[now][j]) {
REP(l, kyori[now][k]) {
an.push_back(k);
cntr++;
}
now = k;
ca[k] = 0;
car[k] = kar;
}
}
REP(j, max(0, cntr - 1)) {
i++;
if (deri[i] != 0) {
st[deri[i]]++;
store[deri[i]].push_back(i);
}
}
}

tmp = an;
}


//0に帰るときに同じ長さで隣にあるなら行ってみる。
void beam_search7(int beam, int time_h, int time_loss) {

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) {
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) {
an.push_back(-1);
continue;
}
int cnt = 0;

VQQ q(time_h + 510);
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 + 500)) {
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];
ll aaa = j;
VI vvv = v;
ll point4 = point1;
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;
ll ab = (l - i - j - kyori[v.back()][k]);
point3 -= ab * ab;
}
}
}
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;
}
}
}
//=======================================================================================================
now = v.back();
while (now != 0) {
if (check_ca[keiro[now][0][0]]) {
aaa += kyori[now][keiro[now][0][0]];
for (int l : car[keiro[now][0][0]]) {
point4 += 100000000LL;
ll ab = (l - i - aaa);
point4 -= ab * ab;
}
vvv.push_back(keiro[now][0][0]);
now = keiro[now][0][0];
check_ca[now] = false;
}
else {
bool b = true;
for (pair<int, int> k : G[now]) {
if (check_ca[k.first]) {
if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
aaa += kyori[now][k.first];
for (int l : car[k.first]) {
point4 += 100000000LL;
ll ab = (l - i - aaa);
point4 -= ab * ab;
}
vvv.push_back(k.first);
now = k.first;
check_ca[now] = false;
b = false;
break;
}
}
}
if (b) {
aaa += kyori[now][keiro[now][0][0]];
now = keiro[now][0][0];
vvv.push_back(now);
check_ca[now] = false;
}
}
}
if (i +aaa < 9525) {
if (aaa < time_h) {
if (point4 > cur) {
cur = point4;
time_cur = aaa;
as = vvv;
}
}
else {
if (point4*time_cur > aaa*cur) {
cur = point4;
as = vvv;
time_cur = aaa;
}
}
}
//=======================================================================================================
}



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]) {
ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
point2 += 100000000;
point2 -= ab * ab;
}
VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 500) {
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 aaa = j;
VI vvv = v;
ll point3 = point1;
ll point4 = 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;
ll ab = l - i - j - kyori[v.back()][k];
point3 -= ab * ab;
}
}
}
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;
}
}
}
//=======================================================================================================
now = v.back();
while (now != 0) {
if (check_ca[keiro[now][0][0]]) {
aaa += kyori[now][keiro[now][0][0]];
for (int l : car[keiro[now][0][0]]) {
point4 += 100000000LL;
ll ab = (l - i - aaa);
point4 -= ab * ab;
}
vvv.push_back(keiro[now][0][0]);
now = keiro[now][0][0];
check_ca[now] = false;
}
else {
bool b = true;
for (pair<int, int> k : G[now]) {
if (check_ca[k.first]) {
if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
aaa += kyori[now][k.first];
for (int l : car[k.first]) {
point4 += 100000000LL;
ll ab = (l - i - aaa);
point4 -= ab * ab;
}
vvv.push_back(k.first);
now = k.first;
b = false;
check_ca[now] = false;
break;
}
}
}
if (b) {
aaa += kyori[now][keiro[now][0][0]];
now = keiro[now][0][0];
vvv.push_back(now);
check_ca[now] = false;
}
}
}
if (i + aaa < 9525) {
if (aaa < time_h) {
if (point4 > cur) {
cur = point4;
time_cur = aaa;
as = vvv;
}
}
else {
if (point4*time_cur > aaa*cur) {
cur = point4;
as = vvv;
time_cur = aaa;
}
}
}
//=======================================================================================================
}


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 ab = i + j + kyori[k][v[v.size() - 1]] - l;
point2 -= ab * ab;
}

VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 500) {
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 ab = i + j + kyori[k][v.back()] - l;
point2 -= ab * ab;
}
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) {
an.push_back(-1);
continue;
}

int cntr = 0;
as.erase(as.begin());
for (int j : as) {
for (int k : keiro[now][j]) {
REP(l, kyori[now][k]) {
an.push_back(k);
cntr++;
}
now = k;
ca[k] = 0;
car[k] = kar;
}
}
REP(j, max(0, cntr - 1)) {
i++;
if (deri[i] != 0) {
st[deri[i]]++;
store[deri[i]].push_back(i);
}
}
}

tmp = an;
}


//0に帰るときに同じ長さで隣にあるなら行ってみる。
void beam_search8(int beam, int time_h, int time_loss) {

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) {
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) {
an.push_back(-1);
continue;
}
int cnt = 0;

VQQ q(time_h + 510);
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 + 500)) {
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];
ll aaa = j;
VI vvv = v;
ll point4 = point1;
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;
ll ab = (l - i - j - kyori[v.back()][k]);
point3 -= ab * ab;
}
}
}
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;
}
}
}
//=======================================================================================================
now = v.back();
while (now != 0) {
priority_queue<pair<ll,pair<ll, int>>> qp;
qp.push({ 0,{0,keiro[now][0][0]} });
for (pair<int, int> k : G[now]) {
if (check_ca[k.first]) {
if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
ll point5 = 0;
ll point6 = 0;
ll aaaa = aaa + kyori[now][k.first];
for (int l : car[k.first]) {
point5 += 100000000LL;
point6 += 100000000LL;
ll ab = (l - i - aaaa);
point5 += ab * ab;
point6 -= ab * ab;

}
qp.push({ point5,{point6,k.first} });
}
}
}
aaa += kyori[qp.top().second.second][now];
point4 += qp.top().second.first;
now = qp.top().second.second;
check_ca[now] = false;
vvv.push_back(now);
}
if (i + aaa < 9525) {
if (aaa < time_h) {
if (point4 > cur) {
cur = point4;
time_cur = aaa;
as = vvv;
}
}
else {
if (point4*time_cur > aaa*cur) {
cur = point4;
as = vvv;
time_cur = aaa;
}
}
}
//=======================================================================================================
}



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]) {
ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
point2 += 100000000;
point2 -= ab * ab;
}
VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 500) {
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 aaa = j;
VI vvv = v;
ll point3 = point1;
ll point4 = 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;
ll ab = l - i - j - kyori[v.back()][k];
point3 -= ab * ab;
}
}
}
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;
}
}
}
//=======================================================================================================
now = v.back();
while (now != 0) {
priority_queue<pair<ll, pair<ll, int>>> qp;
qp.push({ 0,{0,keiro[now][0][0]} });
for (pair<int, int> k : G[now]) {
if (check_ca[k.first]) {
if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
ll point5 = 0;
ll point6 = 0;
ll aaaa = aaa + kyori[now][k.first];
for (int l : car[k.first]) {
point5 += 100000000LL;
point6 += 100000000LL;
ll ab = (l - i - aaaa);
point5 += ab * ab;
point6 -= ab * ab;

}
qp.push({ point5,{point6,k.first} });
}
}
}
aaa += kyori[qp.top().second.second][now];
point4 += qp.top().second.first;
now = qp.top().second.second;
check_ca[now] = false;
vvv.push_back(now);
}
if (i + aaa < 9525) {
if (aaa < time_h) {
if (point4 > cur) {
cur = point4;
time_cur = aaa;
as = vvv;
}
}
else {
if (point4*time_cur > aaa*cur) {
cur = point4;
as = vvv;
time_cur = aaa;
}
}
}
//=======================================================================================================
}


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 ab = i + j + kyori[k][v[v.size() - 1]] - l;
point2 -= ab * ab;
}

VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 500) {
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 ab = i + j + kyori[k][v.back()] - l;
point2 -= ab * ab;
}
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) {
an.push_back(-1);
continue;
}

int cntr = 0;
as.erase(as.begin());
for (int j : as) {
for (int k : keiro[now][j]) {
REP(l, kyori[now][k]) {
an.push_back(k);
cntr++;
}
now = k;
ca[k] = 0;
car[k] = kar;
}
}
REP(j, max(0, cntr - 1)) {
i++;
if (deri[i] != 0) {
st[deri[i]]++;
store[deri[i]].push_back(i);
}
}
}

tmp = an;
}

void beam_search9(int beam, int time_h, int time_loss) {

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) {
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) {
an.push_back(-1);
continue;
}
int cnt = 0;

VQQ q(time_h + 510);
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 + 500)) {
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];
ll aaa = j;
VI vvv = v;
ll point4 = point1;
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;
ll ab = (l - i - j - kyori[v.back()][k]);
point3 -= ab * ab;
}
}
}
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;
}
}
}
now = v.back();
while (now != 0) {
priority_queue<pair<ll, pair<ll, int>>> qp;
qp.push({ 0,{0,keiro[now][0][0]} });
for (pair<int, int> k : G[now]) {
if (check_ca[k.first]) {
if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
ll point5 = 0;
ll point6 = 0;
ll aaaa = aaa + kyori[now][k.first];
for (int l : car[k.first]) {
point5 += 100000000LL;
point6 += 100000000LL;
ll ab = (l - i - aaaa);
point5 += ab * ab;
point6 -= ab * ab;

}
qp.push({ point5,{point6,k.first} });
}
}
}
aaa += kyori[qp.top().second.second][now];
point4 += qp.top().second.first;
now = qp.top().second.second;
check_ca[now] = false;
vvv.push_back(now);
}
if (i + aaa < 9525) {
if (aaa < time_h) {
if (point4 > cur) {
cur = point4;
time_cur = aaa;
as = vvv;
}
}
else {
if (point4*time_cur > aaa*cur) {
cur = point4;
as = vvv;
time_cur = aaa;
}
}
}
}



//=======================================================================================================



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]) {
ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
point2 += 100000000;
point2 -= ab * ab;
}
VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 500) {
bool b = true;
int ti1 = j + kyori[k][v.back()];
REP(l, q[ti1].size()) {
if (q[ti1][l].second.back() == k) {
VI vvv1 = vvv;
VI vvv2 = q[ti1][l].second;
sort(ALL(vvv1));
sort(ALL(vvv2));
if (vvv1 == vvv2) {
b = false;
if (point2 > q[ti1][l].first) {
q[ti1][l] = { point2,vvv };
sort(ALL(q[ti1]));
reverse(ALL(q[ti1]));
}
break;
}
}
}
if (b) {
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 aaa = j;
VI vvv = v;
ll point3 = point1;
ll point4 = 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;
ll ab = l - i - j - kyori[v.back()][k];
point3 -= ab * ab;
}
}
}
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;
}
}
}
now = v.back();
while (now != 0) {
priority_queue<pair<ll, pair<ll, int>>> qp;
qp.push({ 0,{0,keiro[now][0][0]} });
for (pair<int, int> k : G[now]) {
if (check_ca[k.first]) {
if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
ll point5 = 0;
ll point6 = 0;
ll aaaa = aaa + kyori[now][k.first];
for (int l : car[k.first]) {
point5 += 100000000LL;
point6 += 100000000LL;
ll ab = (l - i - aaaa);
point5 += ab * ab;
point6 -= ab * ab;

}
qp.push({ point5,{point6,k.first} });
}
}
}
aaa += kyori[qp.top().second.second][now];
point4 += qp.top().second.first;
now = qp.top().second.second;
check_ca[now] = false;
vvv.push_back(now);
}
if (i + aaa < 9525) {
if (aaa < time_h) {
if (point4 > cur) {
cur = point4;
time_cur = aaa;
as = vvv;
}
}
else {
if (point4*time_cur > aaa*cur) {
cur = point4;
as = vvv;
time_cur = aaa;
}
}
}
}




//=======================================================================================================





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 ab = i + j + kyori[k][v[v.size() - 1]] - l;
point2 -= ab * ab;
}

VI vvv = v;
vvv.push_back(k);
if (j + kyori[k][v.back()] < time_h + 500) {
bool b = true;
int ti1 = j + kyori[k][v.back()];
REP(l, q[ti1].size()) {
if (q[ti1][l].second.back() == k) {
VI vvv1 = vvv;
VI vvv2 = q[ti1][l].second;
sort(ALL(vvv1));
sort(ALL(vvv2));
if (vvv1 == vvv2) {
b = false;
if (point2 > q[ti1][l].first) {
q[ti1][l] = { point2,vvv };
sort(ALL(q[ti1]));
reverse(ALL(q[ti1]));
}
break;
}
}
}
if (b) {
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 ab = i + j + kyori[k][v.back()] - l;
point2 -= ab * ab;
}
VI vvv = v;
vvv.push_back(k);
if (i + j + kyori[k][v.back()] < T) {
bool b = true;
int ti1 = j + kyori[k][v.back()];
REP(l, q[ti1].size()) {
if (q[ti1][l].second.back() == k) {
VI vvv1 = vvv;
VI vvv2 = q[ti1][l].second;
sort(ALL(vvv1));
sort(ALL(vvv2));
if (vvv1 == vvv2) {
b = false;
if (point2 > q[ti1][l].first) {
q[ti1][l] = { point2,vvv };
sort(ALL(q[ti1]));
reverse(ALL(q[ti1]));
}
break;
}
}
}
if (b) {
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) {
an.push_back(-1);
continue;
}

int cntr = 0;
as.erase(as.begin());
for (int j : as) {
for (int k : keiro[now][j]) {
REP(l, kyori[now][k]) {
an.push_back(k);
cntr++;
}
now = k;
ca[k] = 0;
car[k] = kar;
}
}
REP(j, max(0, cntr - 1)) {
i++;
if (deri[i] != 0) {
st[deri[i]]++;
store[deri[i]].push_back(i);
}
}
}

tmp = an;
}



int main() {

nyuuryoku();

saitankeiro();

beam_search6(12, 25);
 	calc();
REP(i, 10000) {
if (ans[i] != -1)cout << ans[i] + 1 << endl;
else cout << -1 << endl;
}


}

Measured memory_bytes: 21472