A là một cậu bé đam mê tốc độ và những buổi biểu diễn đua xe tại trường đua. Hôm nay là ngày tổ chức sự kiện đua xe hằng năm, A có dự định sẽ đến trường đua gần nhà để xem những màn đua xe đẹp mắt.

Trường đua có dạng cây gồm ~n~ đỉnh đánh số từ ~1~ đến ~n~. Có ~m~ tay đua, tay đua thứ ~i~ sẽ trình diễn đua xe từ đỉnh ~u_i~ đến đỉnh ~v_i~ tại mốc thời gian ~t_i~ (đơn vị thời gian) với vận tốc không đổi ~s_i~ (cạnh / đơn vị thời gian). Trước mốc thời gian ~t_i~, xem như tay đua chưa xuất hiện trên trường đua.

Vì rất háo hức được thấy các tay lái, A muốn lựa chọn chỗ ngồi trong số ~n~ đỉnh của trường đua sao cho thời gian nhìn thấy được một tay đua bất kỳ là sớm nhất. Biết trước thời gian chạy của từng tay đua, bạn hãy giúp A tính toán xem với mỗi đỉnh thì thời gian sớm nhất gặp được một tay đua bất kỳ tính từ mốc thời gian ~0~ là bao nhiêu nhé.

Input

Dòng đầu tiên chứa một số nguyên ~T~ (~1 \le T \le 100~) cho biết số lượng test. Mỗi test được miêu tả như sau:

Dòng đầu tiên của mỗi test chứa một số nguyên dương ~n~ (~1\le n \le 2\times 10^5~).

~n-1~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương lần lượt là ~u~, ~v~ và ~w~ (~1\le w\le 10^9~) cho biết trong cây có một cạnh nối giữa ~u~ và ~v~ với độ dài ~w~.

Dòng tiếp theo chứa số nguyên dương ~m~ (~1\le m \le 2\times 10^5~).

Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa 4 số nguyên dương lần lượt là ~u_i~, ~v_i~, ~t_i~ và ~s_i~ (~1\le t_i, s_i \le 10^9~) cho biết thông tin của tay đua thứ ~i~.

Dữ liệu đảm bảo tổng các ~n~ và tổng các ~m~ trong số ~T~ test không vượt quá ~2\times 10^5~.

Output

Với mỗi test, in ra ~n~ dòng, dòng thứ ~i~ là thời gian sớm nhất mà đỉnh ~i~ nhìn thấy một tay đua bất kỳ, nếu không có tay đua nào xuất hiện, hay in ra ~-1~. Đáp án sẽ được chấp nhận nếu sai số không quả ~10^{-6}~.

Scoring

Sample Input 1

1
5
1 2 3
1 3 5
3 4 1
4 5 4
3
2 1 3 4
4 2 1 3
1 3 2 6

Sample Output 1

2.0000000
3.0000000
1.3333333
1.0000000
-1