Canh tác lương thực

Trong một vương quốc có $N$ vùng, được đánh số từ $1$ đến $N$, vùng được đánh số $1$ là kinh đô của vương quốc. Có đúng $N-1$ con đường nối trực tiếp giữa các vùng với nhau đảm bảo mỗi vùng đều có thể tới kinh đô thông qua các con đường này. Vương quốc thực hiện phương cách quản lý phân cấp từ kinh đô tới các vùng bên dưới. Cụ thể, vùng $X$ được gọi là quản lý vùng $Y$ nếu mọi cách di chuyển thông qua các con đường từ vùng $Y$ tới kinh đô đều luôn đi qua vùng $X$.

Các vùng đều có các thửa ruộng có thể canh tác lương thực trên đó, vùng thứ $i$ $(1\le i\le N)$ có $Q_i$ thửa ruộng, mỗi thửa ruộng nếu canh tác dự kiến sẽ cho sản lượng đúng $W_i$ tấn. Nhà vua mong muốn tổng sản lượng lương thực trên toàn vương quốc phải đạt tối thiểu $S$ tấn, biết rằng:

• Do đặc thù mỗi vùng, vùng thứ $i$ nếu sử dụng $K_i$ thửa ruộng để canh tác lương thực sẽ tốn tổng chi phí canh tác và bảo vệ mùa màng là $K_i^2\times C_i$.
• Nếu vùng $X$ không sử dụng thửa ruộng nào để canh tác lương thực thì tất cả các vùng mà $X$ quản lý cũng đều không canh tác lương thực.

Yêu cầu: Hãy giúp nhà vua xác định dãy $(K_1,K_2,\dots ,K_N)$ là số lượng thửa ruộng tương ứng được phân công canh tác cho từng vùng, sao cho tổng chi phí canh tác và bảo vệ mùa màng là nhỏ nhất mà vẫn đạt được sản lượng mong muốn của nhà vua, hoặc thông báo là không có cách phân công nào thỏa mãn.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương $N$ và $S$ $(N,S\le 5000)$.
• Dòng thứ $i$ trong số $N$ dòng tiếp theo ghi ba số nguyên dương $Q_i,W_i$ và $C_i$ $(Q_i,W_i\le 5000;C_i\le {10}^6)$.
• Mỗi dòng trong $N-1$ dòng tiếp theo ghi hai số nguyên dương $u$ và $v$ $(1\le u,v\le N)$ thể hiện có con đường nối trực tiếp giữa hai vùng $u$ và $v$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng chi phí canh tác và bảo vệ mùa màng nhỏ nhất tìm được. In ra $-1$ nếu không có phương án phân công nào thỏa mãn.

Ràng buộc

• $1\le N,S\le 5000$.
• $1\le Q_i,W_i\le 5000$; $1\le C_i\le {10}^6$.
• $1\le u,v\le N$; các con đường tạo thành một cây.

Subtasks

• Subtask 1 ($16\%$ số điểm): $Q_i=1$ với mọi $i=1,2,\dots ,N$, và có các con đường trực tiếp từ kinh đô đến tất cả các vùng khác.
• Subtask 2 ($14\%$ số điểm): $N,S\le 500$.
• Subtask 3 ($20\%$ số điểm): $Q_i=W_i=1$ với mọi $i=1,2,\dots ,N$.
• Subtask 4 ($16\%$ số điểm): $Q_i=1$ với mọi $i=1,2,\dots ,N$.
• Subtask 5 ($20\%$ số điểm): Có các con đường trực tiếp từ kinh đô đến tất cả các vùng khác.
• Subtask 6 ($14\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ