Đoán xem nào? Vào năm 6202, máy chủ của Little Cyan Fish đang chào đón thành viên thứ $10^6$! Chưa từng nghe về nó sao? À, máy chủ này, còn được gọi là nhóm của Qingyu, là nơi bạn bè của cậu ấy tụ tập và trò chuyện về lập trình thi đấu, chuyện ngoài lập trình thi đấu, những câu chuyện cười về PKU, ẩm thực Bắc Kinh, và hầu như mọi thứ khác. Nhưng quan trọng nhất, cuộc trò chuyện mỗi ngày đều tràn ngập những tin nhắn về việc ai là thần tượng của ai.

Theo truyền thống, Little Cyan Fish đang tổ chức một bữa tiệc thần tượng với $n$ thành viên, được đánh số từ $1$ đến $n$. Có $m$ mối quan hệ người hâm mộ–thần tượng giữa các thành viên này: trong mối quan hệ thứ $i$, thành viên $u_i$ là người hâm mộ của thành viên $v_i$, và một món quà từ $u_i$ tặng cho $v_i$ có chi phí là $w_i$. Tại bữa tiệc, mỗi thành viên phải tặng đúng một món quà đặc biệt cho một trong những thần tượng của mình. Tuy nhiên, hai thành viên trao đổi quà cho nhau sẽ khá ngượng ngùng (mặc dù nghe cũng khá ngọt ngào đấy :p), vì vậy không có cặp thành viên nào được phép tặng quà cho nhau.

Hãy tìm tổng chi phí tối thiểu của các món quà, hoặc xác định rằng không tồn tại cách sắp xếp hợp lệ nào.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T$), số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu tiếp theo như sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), lần lượt là số lượng thành viên và số lượng mối quan hệ người hâm mộ–thần tượng.

Dòng thứ $i$ trong $m$ dòng tiếp theo chứa ba số nguyên $u_i$, $v_i$, và $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), trong đó thành viên $u_i$ là người hâm mộ của thành viên $v_i$, và một món quà từ $u_i$ tặng cho $v_i$ có chi phí là $w_i$.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$, và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $10^6$. Dữ liệu đảm bảo rằng mỗi cặp có thứ tự $(u_i, v_i)$ xuất hiện nhiều nhất một lần trong một bộ dữ liệu. Hai thành viên có thể là người hâm mộ của nhau.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một số nguyên — tổng chi phí tối thiểu có thể của các món quà. Nếu không có lời giải, hãy in ra $-1$. In mỗi câu trả lời trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
-1
1

Ghi chú

Ở bộ dữ liệu ví dụ đầu tiên, thành viên $1$ tặng quà cho thành viên $2$, thành viên $2$ tặng cho thành viên $3$, và thành viên $3$ tặng cho thành viên $1$. Tổng chi phí là $1 + 2 + 3 = 6$.

Ở bộ dữ liệu ví dụ thứ hai, hai thành viên $1$ và $2$ sẽ buộc phải tặng quà cho nhau, vì vậy không tồn tại cách sắp xếp hợp lệ nào.

Ở bộ dữ liệu ví dụ thứ ba, thành viên $1$ tặng quà cho thành viên $3$, thành viên $2$ tặng cho thành viên $1$, và thành viên $3$ tặng cho thành viên $2$. Tổng chi phí là $1$.