Trong khu vực được xét có n thành phố, đánh số từ đến . Các thành phố được nối với nhau bằng tuyến đường một chiều. Với mỗi tuyến đường người ta cho biết thành phố xuất phát, thành phố đích và độ dài của nó. Giữa hai thành phố có thể có nhiều tuyến đường nối.
Đường đi ngắn nhất từ tới là đường mà tổng độ dài các tuyến đi qua là nhỏ nhất.
Mỗi tuyến đường có thể thuộc một hoặc nhiều đường đi ngắn nhất giữa các cặp thành phố.
Yêu cầu: Cho và thông tin về mỗi tuyến đường. Với mỗi tuyến hãy xác định số lượng đường ngắn nhất mà tuyến đó tham gia. Số này có thể rất lớn nên bạn chỉ cần đưa ra số dư của kết quả tìm được khi chia cho .
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và ;
Mỗi dòng trong dòng sau chứa ba số nguyên xác định điểm đầu, điểm cuối và độ dài con đường (độ dài không vượt quá ).
Dữ liệu ra:
Đưa ra dòng, mỗi dòng chứa một số nguyên, dòng thứ xác định kết quả tìm được với tuyến đường .
