Động đất

Đất nước AZ có $n$ thành phố vừa phải hứng chịu một trận động đất mạnh. Nhiều tòa nhà và các công trình công cộng bị phá hủy, làm tê liệt toàn bộ hệ thống giao thông giữa các thành phố. Sau những nỗ lực của chính phủ, có $n-1$ con đường hai chiều nối giữa $n$ thành phố được sửa chữa để đảm bảo tính liên thông đi lại giữa $n$ thành phố. Các thành phố được đánh số từ $1$ đến $n$. Con đường thứ $k$ $(k=1,2,\dots ,n-1)$ nối hai thành phố $i_k$ và $j_k$ có độ dài $d(i_k,j_k)$ km. Theo dự báo, trong thời gian tới có thể xảy ra một trận động đất nữa, do đó, chính phủ đang lên kế hoạch ứng phó. Theo thông tin thu nhận được, hiện tại thành phố $i$ $(i=1,2,\dots ,n)$ đang có $p_i$ nhân viên cứu hộ. Chính phủ muốn điều chỉnh lại số lượng nhân viên cứu hộ ở các thành phố sao cho độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất. Độ chênh lệch nhân viên cứu hộ giữa các thành phố được tính bằng hiệu số nhân viên cứu hộ ở thành phố có nhiều nhân viên nhất với thành phố có ít nhân viên nhất.

Tại mỗi thành phố đều có xe dùng để vận chuyển nhân viên cứu hộ (giả thiết số xe tại mỗi thành phố đủ nhiều để phục vụ vận chuyển), mỗi xe có khả năng vận chuyển không quá $c$ nhân viên cứu hộ. Nếu muốn vận chuyển $q$ nhân viên cứu hộ từ thành phố $i$ sang thành phố $j$ bằng đường nối trực tiếp thì thành phố $i$ sẽ cần $\lceil q/c\rceil$ xe, trong đó $\lceil x\rceil$ là số nguyên nhỏ nhất không nhỏ hơn $x$ và độ dài đường đi mà mỗi xe phải đi là $d(i,j)$. Sau khi đến thành phố $j$, các nhân viên cứu hộ sẽ ở lại hoặc có thể tiếp tục di chuyển sang thành phố khác bằng xe của thành phố $j$. Để tiết kiệm chi phí vận chuyển, chính phủ cần xây dựng phương án vận chuyển sao cho tổng độ dài đường đi của các xe dùng để vận chuyển là ngắn nhất mà vẫn thỏa mãn yêu cầu nêu trên.

Yêu cầu: Cho thông tin về $n-1$ con đường và số nhân viên cứu hộ tại mỗi thành phố. Hãy tìm phương án vận chuyển nhân viên cứu hộ mà tổng độ dài đường đi của các xe dùng vận chuyển là ngắn nhất mà vẫn đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n$ và $c$ $(c\le {10}^6)$;
• Dòng thứ hai gồm $n$ số nguyên không âm $p_1,p_2,\dots ,p_n$ $(p_i\le {10}^6)$;
• Dòng thứ $k$ trong số $n-1$ dòng tiếp theo chứa ba số nguyên $i_k,j_k,d(i_k,j_k)$ thỏa mãn $1\le i_k<j_k\le n$ và $0<d(i_k,j_k)\le {10}^6$.

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

Dữ liệu ra

• Dòng đầu chứa một số nguyên là tổng độ dài ngắn nhất của các xe dùng để vận chuyển đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất;
• Dòng thứ hai chứa số nguyên $s$ là số lượng đợt vận chuyển;
• Dòng thứ $h$ trong $s$ dòng tiếp theo chứa ba số nguyên dương $i_h,j_h,q_h$, nghĩa là thành phố $i_h$ sẽ có các xe vận chuyển $q_h$ nhân viên cứu hộ sang thành phố $j_h$ (giá trị $q_h$ phải nhỏ hơn hoặc bằng số lượng nhân viên của thành phố $i_h$ tại thời điểm vận chuyển).

Các đợt vận chuyển được thực hiện lần lượt theo thứ tự in ra; mỗi đợt đi trên một con đường nối trực tiếp $i_h$ và $j_h$. Nếu có nhiều phương án tối ưu, in ra phương án bất kỳ.

Ràng buộc

• $1\le n\le 3000$; $1\le c\le {10}^6$;
• $0\le p_i\le {10}^6$;
• $1\le i_k<j_k\le n$, $0<d(i_k,j_k)\le {10}^6$; các con đường đảm bảo đi lại được giữa hai thành phố bất kỳ.

Subtasks

• Subtask 1 ($20\%$ số test, $20\%$ số điểm): $n=3$;
• Subtask 2 ($40\%$ số test, $40\%$ số điểm): $n\le 3000$ và mỗi thành phố có không quá $2$ đường nối trực tiếp tới thành phố khác;
• Subtask 3 ($40\%$ số test, $40\%$ số điểm): $n\le 3000$.

Đối với mỗi test, nếu đưa ra đúng giá trị tổng độ dài ngắn nhất của các xe dùng để vận chuyển, bạn sẽ được $70\%$ số điểm của test đó, nếu tiếp tục đưa ra được một phương án vận chuyển đúng, bạn sẽ được $30\%$ số điểm còn lại.

Ví dụ