#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 3e2 + 7;
const ll inf = 4e18 + 7;
vector<int> ans[10];
ll mn[mxN][mxN], cost[mxN][10];
void Anna(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
mn[i][j] = inf;
mn[i][i] = 0;
}
for (int i = 0; i < m; i++)
mn[a[i]][b[i]] = c[i];
for (int i = 0; i < k; i++)
mn[a[i]][b[i]] = inf;
// Floyd tim min dis
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int u = 0; u < n; u++)
mn[j][u] = min(mn[j][u], mn[j][i] + mn[i][u]);
}
}
// cost[i][j] truy van s[i] -> t[i] di qua canh u[j]
for (int i = 0; i < q; i++)
{
for (int j = 0; j < k; j++)
cost[i][j] = mn[s[i]][a[u[j]]] + mn[b[u[j]]][t[i]];
cost[i][k] = mn[s[i]][t[i]];
ans[0].push_back(i);
}
vector<ii> mem;
for (int i = 1; i <= k; i++)
{
ll tmp = 0;
if (i < k)
tmp = c[u[i]];
vector<int> rem;
for (int j = 0; j < i; j++)
{
for (int v : ans[j])
{
if (cost[v][j] + c[u[j]] < cost[v][i] + tmp)
rem.push_back(v);
else
ans[i].push_back(v);
}
mem.push_back({ans[j].size(), rem.size()});
ans[j] = rem;
}
}
reverse(mem.begin(), mem.end());
ll mask = 0;
for (ii i : mem)
mask = mask * i.fi + i.se;
while (mask)
{
Tap(mask & 1);
mask >>= 1;
}
}
#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 3e2 + 7;
const ll inf = 4e18 + 7;
ll mn[mxN][mxN], cost[mxN][mxN];
vector<ii> w[mxN];
vector<int> ans[10];
int trace[mxN][mxN], a[mxN], b[mxN], c[mxN], edge[100];
void Dij(int n, int stt)
{
for (int i = 0; i < n; i++)
mn[stt][i] = inf;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, stt});
mn[stt][stt] = 0;
while (pq.size())
{
ii j = pq.top();
pq.pop();
if (j.fi != mn[stt][j.se])
continue;
for (ii i : w[j.se])
{
if (mn[stt][i.fi] > j.fi + c[i.se])
{
mn[stt][i.fi] = j.fi + c[i.se];
trace[stt][i.fi] = i.se;
pq.push({mn[stt][i.fi], i.fi});
}
}
}
}
void Trace(int v, int u)
{
vector<int> ans;
while (v != u)
{
ans.push_back(trace[u][v]);
v = a[trace[u][v]];
}
reverse(ans.begin(), ans.end());
for (int i : ans)
cout << i << " ";
}
void Bruno(int n, int m, int A[], int B[], long long C[], int q, int s[], int t[], int k, int u[], int l, ll x[])
{
for (int i = 0; i < m; i++)
{
a[i] = A[i];
b[i] = B[i];
c[i] = C[i];
if (c[i] != -1)
w[a[i]].push_back({b[i], i});
}
for (int i = 0; i < n; i++)
Dij(n, i);
// cost[i][j] truy van s[i] -> t[i] di qua canh u[j]
for (int i = 0; i < q; i++)
{
for (int j = 0; j < k; j++)
cost[i][j] = mn[s[i]][a[u[j]]] + mn[b[u[j]]][t[i]];
cost[i][k] = mn[s[i]][t[i]];
ans[0].push_back(i);
}
ll mask = 0;
for (int i = 0; i < l; i++)
mask += (x[i] << i);
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < i; j++)
{
sort(ans[j].begin(), ans[j].end(), [&](int u, int v)
{
return (cost[u][j] - cost[u][i]) < (cost[v][j] - cost[v][i]);
});
int rem = mask % ans[j].size();
while (ans[j].size() > rem)
{
ans[i].push_back(ans[j].back());
ans[j].pop_back();
}
mask /= ans[j].size();
}
}
for (int i = 0; i <= k; i++)
{
for (int j : ans[i])
edge[j] = i;
}
for (int i = 0; i < q; i++)
{
// s[i], t[i];
if (edge[i] == k)
Trace(t[i], s[i]);
else
{
Trace(a[edge[i]], s[i]);
cout << edge[i] << " ";
Trace(b[edge[i]], t[i]);
}
cout << '\n';
}
}
