Subtask 1: ~\sum n, \sum m \le 5 \times 10^3~.

Với mỗi tay lái, ta tính toán thời gian cho các đỉnh anh ấy đi qua và cập nhập lại thời gian cho đỉnh ấy.

Subtask 2: Vận tốc của các tay đua trong một test như nhau.

Khi tay lái đi từ đỉnh ~u~ đến đỉnh ~v~ sẽ đi lên đến khi gặp cha con chung gần nhất và đi xuống lại cho đến khi gặp v. Ta cần tìm đỉnh ~z = LCA(u, v)~, ta có thể tính thời gian đi từ đỉnh ~u~ đến một đỉnh ~k~ bất kỳ trên đường đi đến ~z~ theo công thức sau:

Với ~t_u = t~: $$t_x = t_u + \frac{distance(u, k)}{s}$$ $$= t_u + \frac{(depth[u] - depth[k])}{s}$$ $$= (t_u + \frac{depth[u]}{s}) - \frac{1}{s} \cdot depth[k]$$

Tương tự cho trường hợp đi từ ~v~ đến ~z~ thì ta chỉ cần thay ~t_u~ bởi ~t_v = t + \frac{distance(u, v)}{s}~:

$$t_x = t_v - \frac{distance(u, k)}{s}$$ $$= t_u - \frac{(depth[u] - depth[k])}{s}$$ $$= (t_u - \frac{depth[u]}{s}) + \frac{1}{s} \cdot depth[k]$$

Có thể coi đây như phương trình đường thẳng ~y = C + M \cdot x~ với:

• ~C = t_u + \frac{depth[u]}{s}~

• ~M = \frac{1}{s}~

• ~x = depth[k]~

Tuy nhiên thì do cùng vận tốc nên hệ số góc của các đường thẳng này chỉ có thể là ~M = \frac{1}{s}~ hoặc ~M = - \frac{1}{s}~, do tất cả đường thẳng cùng hệ số góc sẽ song song với nhau, vì thế ta chỉ cần chọn đường thẳng có hệ số tự do ~C~ nhỏ nhất cho mỗi hệ số góc trên và so sánh kết quả với nhau là tìm được đáp án.

Và để cập nhập đường thẳng cho đoạn từ ~u~ đến ~z~ hay từ ~v~ đến ~z~ ta cần dùng segment tree để cập nhập trên đoạn, tuy nhiên thì các đoạn này không thể xử lí trực tiếp mà phải thông qua tiền xử lí Heavy-Light Decomposition để phân hoạch cây thành cách đoạn con phù hợp để cập nhập.

Subtask 3: Cây có thể biểu diễn thành một đường thẳng.

Ta phân tích cách truy vấn thành các đường thẳng như ở Subtask 2, tuy nhiên ở Subtask này cây có thể biểu diễn thành một đường thẳng nên ta có thể xử lí trực tiếp không cần thông qua Heavy-Light Decomposition.

Tuy nhiên do có sự khác biệt về hệ số góc nên ta cần phải sử dụng Convex Hull Trick để tìm ra thời gian nhỏ nhất để đến các đỉnh là bao nhiêu.

Subtask 4: Không có ràng buộc gì thêm.

Ta làm tương tự như Subtask 2, tuy nhiên do có sự khác biệt về hệ số góc nên ta dùng Convex Hull Trick như ở Subtask 3 là có thể hoàn thành được bài.

#include <bits/stdc++.h>
#define endl '\n'

#define int long long
#define double long double

using namespace std;

template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); } 
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

const int N = 2e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;
const double EPS = 1e-11;

vector <pair<int, int>> a[N];
array<int, 3> edge[N];
int sub[N], h[N], d[N], pa[N];
int szchain[N], ctchain = 1;
int id[N], idchain[N], hd[N], n;
vector <int> ch[N], disch[N];
double ans[N];

struct Line{
    double a, b;

    Line(){
        a = 0; b = INF;
    }
    Line(double a1, double b1){
        a = a1; b = b1;
    }

    double operator()(int x){
        return a * x + b;
    }
};
vector <Line> lichao[N];

void dfs_precal(int u, int par = -1){
    sub[u] = 1;
    for(pair<int, int> st : a[u]){
        int i = st.first, w = st.second;
        if (i == par) continue;

        h[i] = h[u] + 1;
        d[i] = d[u] + w;
        pa[i] = u;

        dfs_precal(i, u);

        sub[u] += sub[i];
    }
}

void dfs_hld(int u, int par = -1, int head = 1, int chain = 1){
    id[u] = szchain[chain]++;
    idchain[u] = chain;
    hd[u] = head;
    ch[chain].push_back(u);

    pair<int, int> ma = {-1, -1};
    for(pair<int, int> st : a[u]){
        int i = st.first;
        if (i == par) continue;

        ma = max(ma, {sub[i], i});
    }
    if (ma.second != -1) dfs_hld(ma.second, u, head, chain);

    for(pair<int, int> st : a[u]){
        int i = st.first;
        if (i == par || i == ma.second) continue;

        dfs_hld(i, u, i, ++ctchain);
    }
}

int cmp(double a, double b){
    if (abs(a - b) <= EPS) return 1;
    if (a < b) return 0;
    else return 2;
}

void upd(vector <Line> &lichao, int idc, int id, int l, int r, Line line){
    if (l == r){
        if (line(disch[idc][l]) < lichao[id](disch[idc][l])){
            lichao[id] = line;
        }
        return;
    }

    int mid = (l + r) >> 1;
    int x = disch[idc][mid];
    if (line.a < lichao[id].a) swap(line, lichao[id]);

    if (cmp(line(x), lichao[id](x)) == 0){
        swap(line, lichao[id]);
        upd(lichao, idc, id << 1 | 1, mid + 1, r, line);
    } else {
        upd(lichao, idc, id << 1, l, mid, line);
    }
}

void upd_range(vector <Line> &lichao, int idc, int id, int l, int r, int u, int v, Line line){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        upd(lichao, idc, id, l, r, line);
        return;
    }

    int mid = (l + r) >> 1;
    upd_range(lichao, idc, id << 1, l, mid, u, v, line);
    upd_range(lichao, idc, id << 1 | 1, mid + 1, r, u, v, line);
}

double get(vector <Line> &lichao, int idc, int id, int l, int r, int pos){
    if (l == r) return lichao[id](disch[idc][pos]);

    int mid = (l + r) >> 1;
    int x = disch[idc][pos];
    if (pos <= mid) return min(lichao[id](x), get(lichao, idc, id << 1, l, mid, pos));
    else return min(lichao[id](x), get(lichao, idc, id << 1 | 1, mid + 1, r, pos));
}

void upd_query(int u, int v, int t, int s){
    double db = (double)1.0 / s;
    bool flip = 0;

    int len = 0, utmp = u, vtmp = v;
    while (hd[u] != hd[v]){
        if (h[hd[u]] < h[hd[v]]) swap(u, v);
        len += abs(d[pa[hd[u]]] - d[u]);

        u = pa[hd[u]];
    }
    len += abs(d[u] - d[v]);

    //dbgm(utmp, vtmp, len);

    u = utmp, v = vtmp;
    int l = 0, r = len;
    while (hd[u] != hd[v]){
        if (h[hd[u]] < h[hd[v]]){
            swap(u, v);
            flip ^= 1;
        }

        int dis = abs(d[hd[u]] - d[u]);
        int rdis = abs(d[pa[hd[u]]] - d[u]);
        int idc = idchain[u];

        if (!flip){
            Line tmp(-db, t + (l + dis) * db);
            //dbgm(u, hd[u], l, r);
            //dbgm(tmp.a, tmp.b);
            upd_range(lichao[idc], idc, 1, 0, szchain[idc] - 1, id[hd[u]], id[u], tmp);

            l += rdis;
        } else {
            Line tmp(db, t + (r - dis) * db);
            //dbgm(u, hd[u], l, r);
            //dbgm(tmp.a, tmp.b);
            upd_range(lichao[idc], idc, 1, 0, szchain[idc] - 1, id[hd[u]], id[u], tmp);

            r -= rdis;
        }

        u = pa[hd[u]];
    }
    if (h[u] > h[v]){
        swap(u, v);// flip ^= 1;
    } else flip ^= 1;
    int dis = abs(d[u] - d[v]), idc = idchain[u];
    int dishd = abs(d[hd[u]] - d[u]);
    if (!flip){
        //
        Line tmp(-db, t + (l + dis + dishd) * db);
        //dbgm(u, v, l, r);
        //dbgm(tmp.a, tmp.b);
        upd_range(lichao[idc], idc, 1, 0, szchain[idc] - 1, id[u], id[v], tmp);
    } else {
        Line tmp(db, t + (r - dis - dishd) * db);
        //dbgm(u, v, l, r);
        //dbgm(tmp.a, tmp.b);
        upd_range(lichao[idc], idc, 1, 0, szchain[idc] - 1, id[u], id[v], tmp);
    }
    //dbg("------------------");
}

void dbglichao(){
    cout << "------------------" << endl;
    cout << "why: " << endl;

    for(int i = 1; i <= ctchain; ++i){
        for(int j : ch[i]){
            ans[j] = get(lichao[idchain[j]], idchain[j], 1, 0, szchain[idchain[j]] - 1, id[j]);
        }
    }

    for(int i = 1; i <= n; ++i){
        if (cmp(ans[i], INF) == 1) cout << -1 << " ";
        else cout << fixed << setprecision(7) << ans[i] << " ";
    }

    cout << "------------------" << endl;
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v, w; cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
        edge[i] = {u, v, w};
    }

    dfs_precal(1);
    dfs_hld(1);

    for(int i = 1; i <= ctchain; ++i){
        lichao[i].resize(4 * szchain[i] + 5);
        for(int j : ch[i]){
            disch[i].push_back(d[j] - d[hd[j]]);
        }
        //dbg(ch[i]);
        //dbg(disch[i]);
    }

    //dbglichao();

    int m; cin >> m;
    for(int i = 1; i <= m; ++i){
        int u, v, t, s;
        cin >> u >> v >> t >> s;

        upd_query(u, v, t, s);
        //dbglichao();
    }

    //return;

    for(int i = 1; i <= ctchain; ++i){
        for(int j : ch[i]){
            ans[j] = get(lichao[idchain[j]], idchain[j], 1, 0, szchain[idchain[j]] - 1, id[j]);
        }
    }

    for(int i = 1; i <= n; ++i){
        if (cmp(ans[i], INF) == 1) cout << -1 << endl;
        else cout << fixed << setprecision(7) << ans[i] << endl;
    }

    ///////////////////////////// reset
    for(int i = 1; i <= n; ++i){
        a[i].clear();
        sub[i] = h[i] = d[i] = pa[i] = szchain[i] = 0;
        ctchain = 1;
        id[i] = idchain[i] = hd[i] = 0;
        ch[i].clear(); disch[i].clear();
        ans[i] = 0;
        lichao[i].clear();
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; cin >> t;
    while (t--)
    {
        solve();
    }
}