Công ty du lịch ~X~ có dự án tổ chức các hành trình du lịch trong vùng lãnh thổ gồm ~n~ điểm du lịch trọng điểm, được đánh số từ ~1~ tới ~n~. Hệ thống giao thông trong vùng gồm ~m~ tuyến đường một chiều khác nhau, tuyến đường thứ ~j~ (~j = 1~, ~2~, ~3~, ..., ~m~) cho phép đi từ địa diểm ~u_{j}~ đến dịa diểm ~v_{j}~ với chi phí đi lại là một số nguyên dương ~c~(~u_{j}~, ~v_{j}~). Vấn đề đặt ra cho công ty là xây dựng các hành trình du lịch cho mỗi điểm du lịch. Một hành trình du lịch cho địa điểm du lịch ~i~ phải được xây dựng sao cho xuất phát từ địa điểm ~i~ đi qua một số địa điểm khác rồi quay lại địa điểm xuất phát ~i~ với tổng chi phí (được tính như là tổng chi phí của các tuyến đường mà hành trình đi qua) nhỏ nhất.

Input

Dòng đầu tiên số ~T~ là số lượng bộ dữ liệu. Tiếp đến là ~T~ nhóm dòng, mỗi dòng cho thông tin về một bộ dữ liệu theo khuôn dạng sau:

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n~, ~m~
• Dòng thứ ~j~ trong số ~m~ dòng tiếp theo chứa ba số nguyên duong ~u_{j}~, ~v_{j}~, ~c~(~u_{j}~, ~v_{j}~) cho biết thông tin về tuyến đường thứ ~j~. Giả thiết là ~u_{j} \neq v_{j}~; ~c~(~u_{j}~, ~v_{j}~) ~< 10^{6}~; ~j = 1~, ~2~, ..., ~m~

Output

Gồm ~T~ nhóm dòng tương ứng với ~T~ bộ test vào, mỗi nhóm dòng gồm ~n~ dòng, dòng thứ ~i~ ghi chi phí của hành trình du lịch cho địa điểm ~i~.

Qui ước: Ghi số ~-1~ trên dòng ~i~ nếu không tìm được hành trình du lịch cho địa điểm ~i~ thỏa mãn yêu cầu đặt ra

Giới hạn

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm của bài có ~n \le 20~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~20 < n \le 100~, ~m \le 10^{4}~.
• Có 40% số test tương ứng với 30% số điểm của bài có ~100 < n \le 10^{3}~, ~m \le 10^{5}~

Sample Input

1
6 8
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7

Sample Output

11
11
6
11
6
-1