Giải bài trực tuyến

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 xấu 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 ≠ 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

Example

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

Output:

11
11
6
11
6
-1

Ràng buộc:
Có 30%      số test tương ứng với 30% số điểm của bài có n <= 20.
Có 30%      số test tương ứng với 30% số điểm của bài có 20 < n <= 100, m <= 104.
Có 40%      số test tương ứng với 30% số điểm của bài có 100 < n <= 103,      m <= 105