Hành trình du lịch

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,\dots ,m$) cho phép đi từ địa điểm $u_j$ đến địa điể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.

Dữ liệu vào

• Dòng đầu tiên là số $T$: số lượng bộ dữ liệu. Tiếp đến là $T$ nhóm dòng, mỗi nhóm 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 dương $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\ne v_j$; $c(u_j,v_j)<{10}^6$; $j=1,2,\dots ,m$.

Dữ liệu ra

Gồm $T$ nhóm dòng tương ứng với $T$ bộ dữ liệu 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$.

Quy ướ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.

Ràng buộc

• $1\le T\le 10$; trong một test, tổng các $n$ không vượt quá $1000$ và tổng các $m$ không vượt quá ${10}^5$.
• $2\le n\le 1000$; $1\le m\le {10}^5$; không có hai tuyến đường cùng đi từ $u$ đến $v$.
• $1\le u_j,v_j\le n$, $u_j\ne v_j$; $1\le c(u_j,v_j)<{10}^6$.

Subtasks

• Subtask 1 ($30\%$ số test): $n\le 20$.
• Subtask 2 ($30\%$ số test): $n\le 100$, $m\le {10}^4$.
• Subtask 3 ($40\%$ số test): $n\le 1000$, $m\le {10}^5$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ