#include using namespace std; using ll = long long; void solve(int n, vector> ed, vector> q) { vector> e(n); for (int i = 0; i < n - 1; i++) { auto &[u, v] = ed[i]; e[u].push_back(v); e[v].push_back(u); } int tmr = 0; vector vis(n); vector sum0(n), sum1(n); vector dist(n); vector> st; auto init = [&]() { sum0.assign(n, 0); sum1.assign(n, 0); }; auto upd = [&](ll &x, ll y) { st.emplace_back(x, x); x = y; }; function dfs1 = [&](int v) { vis[v] = tmr; for (int to : e[v]) { if (vis[to] == tmr) continue; dfs1(to); sum0[v] += sum0[to]; sum1[v] += sum0[to] + sum1[to]; } }; function dfs2 = [&](int v) { vis[v] = tmr; dist[v] = sum1[v]; int csz = st.size(); for (int to : e[v]) { if (vis[to] == tmr) continue; upd(sum1[v], sum1[v] - sum0[to] - sum1[to]); upd(sum0[v], sum0[v] - sum0[to]); upd(sum1[to], sum1[to] + sum0[v] + sum1[v]); upd(sum0[to], sum0[to] + sum0[v]); dfs2(to); while ((int)st.size() > csz) { st.back().first = st.back().second; st.pop_back(); } } }; for (int i = 0; i < n - 1; i++) { auto &[u, v] = ed[i]; e[u].erase(find(e[u].begin(), e[u].end(), v)); e[v].erase(find(e[v].begin(), e[v].end(), u)); init(); ++tmr; dfs1(u); ++tmr; dfs1(v); auto col = vis; for (auto &vct : q) { if (vis[vct[0]] != vis[vct[1]]) { sum0[vct[0]] += vct[2]; sum0[vct[1]] += vct[2]; } } ++tmr; dfs1(u); dfs1(v); ++tmr; dfs2(u); dfs2(v); int nu = u, nv = v; auto upd = [&](int &old, int cand) { if (e[cand].size() >= 3) return; if (dist[cand] < dist[old] || dist[cand] == dist[old] && cand < old) { old = cand; } }; for (int i = 0; i < n; i++) { if (col[i] == col[u]) { upd(nu, i); } else { upd(nv, i); } } if (nu > nv) swap(nu, nv); e[nu].push_back(nv); e[nv].push_back(nu); printf("%d %d\n", nu + 1, nv + 1); } } int main() { int n; scanf("%d", &n); vector> ed; for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d%d", &u, &v); ed.push_back({u - 1, v - 1}); } int d; scanf("%d", &d); vector> q(d, vector(3)); for (int i = 0; i < d; i++) { for (int j = 0; j < 3; j++) { scanf("%d", &q[i][j]); } q[i][0]--; q[i][1]--; } solve(n, ed, q); return 0; }