TOURS13 - VNOI

TOURS13 - VOI 2013 - Hành trình du lịch

Giới hạn

Thời gian: 1.0s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

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 <= 10⁴.
Có 40% số test tương ứng với 30% số điểm của bài có 100 < n <= 10³, m <= 10⁵

Người up: voj
Nguồn bài: VOI 2013 - Ngày 2