Ai cũng biết Alex là một người rất giàu có, anh có đến \(n\) (\(n \le 1155\)) căn nhà (các nhà được đánh số từ \(1\) đến \(n\)). Trước kia, do không chú ý trong lúc xây dựng, nên mỗi nhà đã bị sơn một màu khác nhau, không có nhà nào giống nhà nào. Là một người sống đơn giản, không thích màu mè, nên Alex muốn các căn nhà của mình không được sơn quá nhiều màu.

Để làm được như vậy, anh đã chia \(n\) căn nhà của mình vào \(k\) (\(k \le 15\)) nhóm (mỗi nhà chỉ thuộc một nhóm, và mỗi nhóm chứa ít nhất một căn nhà). Các căn nhà trong cùng một nhóm sẽ được sơn màu giống nhau. Nhưng không bắt buộc hai căn nhà khác nhóm phải được sơn khác màu.

Nhưng do sở hữu quá nhiều nhà, và Alex chỉ muốn kết thúc các việc một cách nhanh gọn, nên Alex đã tìm đến một nhà thông thái. Ông là một người tài ba, thông thạo đến \(m\) (\(m \le 1555\)) phép thần thông biến hóa. Khi xài phép thứ \(i\) (\(i \le m\)), ông chỉ tốn \(c_i\) giây để có thể biến tất cả các nhà có màu \(a_i\) thành màu \(b_i\) và ngược lại. Trong cùng một lúc, ông chỉ đọc được một câu thần chú của một phép biến hóa nào đó. Nhưng bù lại ông luôn biết cách tối ưu hóa trong mọi công việc của mình.

Yêu cầu: Cho biết số nhóm và các căn nhà trong mỗi nhóm. Hãy cho biết thời gian ít nhất để nhà thông thái biến các căn nhà thuộc mỗi nhóm về cùng một màu. Biết ban đầu nhà thứ \(i\) có màu \(i\).

Input

• Dòng đầu tiên chứa hai số nguyên dương: \(n\) - số lượng nhà hiện có, \(k\) - số nhóm phải chia.
• Dòng thứ hai gồm \(n\) số, số thứ \(i\) có giá trị \(e_i\) (\(1 \le i \le n; 1 \le e_i \le k\)) nếu nhà thứ \(i\) thuộc nhóm \(e_i\).
• Dòng thứ ba là số phép biến hóa có thể sử dụng - \(m\).
• \(m\) dòng cuối cùng, mỗi dòng chứa bộ ba các số nguyên không âm \(a_i, b_i, c_i\) (\(1 \le i \le m; 1 \le a_i, b_i \le n; c_i \le 10^9\)) miêu tả một phép biến hóa.

Output

• In ra thời gian ít nhất cần cho vị pháp sư thực hiện ý muốn của Alex (dữ liệu đảm bảo luôn có kết quả).

Example

4 2 
1 1 1 2
4
1 2 3
1 3 3
2 4 2
3 4 2

6

4 2 
1 1 1 2
4
1 2 3
1 3 3
2 4 1
3 4 1

5