Khoá tủ lạnh

Có $n$ người, mỗi người sở hữu một tủ lạnh riêng. Các tủ lạnh được khóa bằng $m$ sợi dây xích thép. Mỗi sợi xích nối hai tủ lạnh khác nhau và được bảo vệ bằng một khóa số. Chủ nhân của tủ lạnh biết mã của tất cả các sợi xích nối tới tủ của mình. Một tủ lạnh chỉ có thể mở được khi tất cả các sợi xích nối tới nó đã được mở khóa.

Cho phép tạo nhiều sợi xích giữa cùng một cặp tủ lạnh.

Tủ lạnh $i$ được gọi là riêng tư nếu chỉ có chủ nhân (người $i$) mới có thể mở nó — không tồn tại người $j\ne i$ nào (một mình) mở được tủ $i$.

Trọng lượng của $n$ tủ lạnh là $a_1,a_2,\dots ,a_n$. Tạo một sợi xích nối tủ $u$ và tủ $v$ tốn $a_u+a_v$ đồng.

Bạn cần tạo đúng $m$ sợi xích sao cho tất cả các tủ lạnh đều riêng tư, với tổng chi phí nhỏ nhất. Nếu không có cách nào thoả mãn, hãy báo cáo điều đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1\le T\le 10$) — số bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng thứ nhất chứa hai số nguyên $n$, $m$ ($2\le n\le 1000$, $1\le m\le n$).
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($0\le a_i\le {10}^4$).

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Nếu không tồn tại cách bố trí thoả mãn, in ra $-1$.
• Ngược lại, in ra một số nguyên $c$ là tổng chi phí nhỏ nhất. Sau đó in ra $m$ dòng, mỗi dòng chứa hai số nguyên $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$) mô tả sợi xích thứ $i$. Có thể có nhiều sợi xích nối cùng một cặp tủ.

Nếu có nhiều đáp án, in ra bất kỳ.

Ràng buộc

• $1\le T\le 10$
• $2\le n\le 1000$
• $1\le m\le n$
• $0\le a_i\le {10}^4$

Ví dụ