Sample Input đúng của bài được đính chính ở dưới.

Alice đã tạo dữ liệu kiểm thử cho một bài toán liên quan đến đồ thị có dạng cây. Cụ thể, đồ thị dạng cây có ~n~ đỉnh, trong đó ~1~ là gốc, có ~n-1~ cạnh, cạnh thứ ~k~ ~(1 \le k \le n-1)~, nối hai đỉnh phân biệt ~u_k, v_k~ ~(1 \le u_k, v_k \le n)~ với trọng số là ~w_k~ (chú ý rằng, ~w_k~ có thể âm). Tuy nhiên, dữ liệu về các cạnh đã bị mất mà Alice chỉ nhớ được các thông tin sau:

• Tổng trọng số của tất cả các cạnh bằng ~s~;

• Với đỉnh ~i~ ~(1 < i \le n)~, tổng trọng số các cạnh đi từ đỉnh gốc ~1~ xuống đỉnh ~i~ bằng ~d_i~;

Yêu cầu: Hãy giúp Alice khôi phục lại cây.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~s~ ~(1 \le n \le 2 \cdot 10^5; 0 \le s \le 2 \cdot 10^5)~;

• Dòng thứ hai chứa ~n~ số nguyên ~d_i~ ~(|d_1| + |d_2| + \dots + |d_n| \le 2 \cdot 10^5)~.

Output

• Gồm ~n-1~ dòng, dòng thứ ~k~ ~(1 \le k \le n-1)~ chứa ba số nguyên ~u_k~ ~v_k~ ~w_k~.

Scoring

Sample Input 1

5 2
0 1 -1 0 0

Sample Output 1

1 2 1
1 3 -1
3 4 1
3 5 1