Cho một đồ thị ~G~ gồm ~n~ đỉnh và ~m~ cạnh hai chiều. Các đỉnh được đánh số từ ~1~ đến ~n~, các cạnh được đánh số từ ~1~ đến ~m~. Cạnh thứ ~i~ nối giữa hai đỉnh ~a_i~ và ~b_i~ và có trọng số ~w_i~. Lưu ý rằng, đồ thị ~G~ có thể là đa đồ thị (có cạnh nối giữa một đỉnh với chính nó, hoặc có nhiều hơn hai cạnh nối cùng một cặp đỉnh).

Giáo sư X vừa phát minh ra một phép toán để nén đồ thị ~G~ như sau:

• Trước hết, cần tô màu cho mỗi đỉnh trong đồ thị ~G~ bằng một trong số các màu từ ~1~ đến ~k~ (các đỉnh có thể có màu khác nhau).
• Sau đó, xây dựng đồ thị ~G'~ gồm ~k~ đỉnh và ~m~ cạnh, trong đó cạnh thứ ~i~ nối giữa hai đỉnh ~x~ và ~y~ và có trọng số ~w_i~ (với ~x~ và ~y~ lần lượt là màu của hai đỉnh ~a_i~ và ~b_i~).
• Đồ thị ~G'~ là kết quả của phép nén đồ thị ~G~.

Hiện tại, đã có một số đỉnh của đồ thị ~G~ được tô màu. Cụ thể, đỉnh ~i~ đã được tô màu ~c_i~ (nếu ~c_i > 0~) hoặc chưa được tô màu nếu ~c_i = 0~. Giáo sư X đưa ra định nghĩa về cây khung nhỏ nhất như sau:

• Cây khung của đồ thị là một tập hợp các cạnh của đồ thị thỏa mãn tập cạnh này không chứa chu trình và liên thông (từ một đỉnh bất kì có thể đi tới bất kỳ đỉnh nào khác theo mà chỉ dùng các cạnh trên cây khung).
• Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh trong cây nhỏ nhất (giá trị tổng này được gọi là trọng số của cây khung).

Yêu cầu: Hãy giúp giáo sư X tô màu các đỉnh còn lại của đồ thị ~G~ sao cho trọng số của cây khung nhỏ nhất của đồ thị ~G'~ là nhỏ nhất có thể, hoặc cho biết rằng không tồn tại cách tô màu để đồ thị ~G'~ có chứa cây khung.

Input

• Dòng đầu tiên gồm số nguyên ~t~ (~1 \le t \le 10~) là số lượng test case. Các test case được cách nhau bằng một dòng trống.
• Dòng đầu tiên của mỗi test case gồm ba số nguyên ~n, m, k~ (~1 \le n, m \le 10^5~, ~1 \le k \le n~) là số đỉnh, số cạnh của đồ thị ~G~, và số màu khác nhau có thể tô cho từng đỉnh.
• Dòng thứ hai gồm ~n~ số nguyên ~c_1, c_2, \dots, c_n~ (~0 \le c_i \le n~) là màu được tô ban đầu của đỉnh ~i~.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo gồm ba số nguyên ~a_i, b_i, w_i~ (~1 \le a_i, b_i \le n~, ~1 \le w_i \le 10^9~) mô tả cạnh thứ ~i~ của đồ thị ~G~.

Output

Với mỗi test case, in ra một số nguyên duy nhất là trọng số nhỏ nhất có thể của cây khung nhỏ nhất của đồ thị ~G'~ với cách tô màu tối ưu, hoặc in ra ~-1~ nếu không tồn tại cách tô màu để đồ thị ~G'~ có chứa cây khung.

Sample Input 1

4
5 6 4
3 2 4 1 2
1 2 9
2 3 5
1 4 8
5 4 6
3 4 3
3 5 2
3 3 2
1 2 0
1 2 5
1 3 3
2 3 2
4 1 3
0 0 0 0
1 2 7
3 3 2
0 2 0
1 2 10
1 2 20
3 3 30

Sample Output 1

13
2
-1
10