공정한 분배

농부 조합은 곡식을 생산해 큰 식품 회사에 납품했고, 회사는 N명의 농부에게 모두 같은 금액 X를 지급했다. 하지만 각 농부가 실제로 기여한 양은 서로 다르므로, 농부들은 받은 돈을 더 공정하게 다시 나누려고 한다.

농부들은 모두 서로 다른 마을에 살고 있다. 마을들은 도로로 연결되어 있으며, 임의의 두 마을 사이에는 정확히 하나의 경로만 존재한다. 한 번의 거래에서 한 농부는 트랙터를 타고 자신의 마을과 도로로 직접 연결된 이웃 마을로 가서, 그 마을의 농부에게 원하는 양의 돈을 건넬 수 있다.

각 농부가 받아야 한다고 생각하는 금액이 주어진다. 프로그램은 다음 두 가지를 구해야 한다.

1. 모든 농부가 자신이 받아야 하는 금액 이상을 갖게 만들기 위해 필요한 거래 횟수의 최솟값
2. 그 최솟값을 달성하는 거래 목록과 순서

거래 순서는 중요하다. 어떤 농부도 현재 가지고 있는 돈보다 더 많은 돈을 줄 수 없다.

식품 회사가 농부들에게 필요한 총액보다 많은 돈을 지급했을 수도 있다. 이 경우 남는 돈은 어디에 있어도 상관없으며, 모든 농부가 자신이 받아야 하는 금액 이상만 가지면 된다.

첫째 줄에 농부의 수 N이 주어진다. (1 <= N <= 2000)

둘째 줄에 각 농부가 처음 받은 금액 X가 주어진다. (0 <= X <= 10000)

셋째 줄에 N개의 정수가 주어진다. i번째 정수는 i번 농부가 받아야 하는 금액이다. 이 N개 정수의 합은 N * X 이하이다.

다음 N - 1개의 줄에는 도로가 주어진다. 각 줄에는 도로가 연결하는 두 마을의 번호 A와 B가 주어진다. 마을 번호는 1 이상 N 이하이며, 도로는 양방향이다.

첫째 줄에 필요한 거래 횟수의 최솟값 K를 출력한다.

다음 K개의 줄에는 거래를 한 줄에 하나씩 출력한다. 각 거래는 세 정수 A, B, C로 나타낸다. 이는 A번 마을의 농부가 B번 마을로 가서 그곳의 농부에게 C만큼의 돈을 준다는 뜻이다. A번 마을과 B번 마을은 도로로 직접 연결되어 있어야 한다.

조건을 만족하는 최적의 거래 목록이나 순서가 여러 가지일 수 있으며, 그중 아무 것이나 출력해도 된다.