Mô tả và yêu cầu

ĐƯỜNG ĐI Tên chương trình: PATHS.???

Trong khu vực được xét có n thành phố, đánh số từ 1 đến n. Các thành phố được nối với nhau
bằng m 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ừ A tới B 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ố. Ví dụ, với mạng lưới giao thông ở
hình bên, tuyến đường từ 1 tới 2 thuộc các đường đi ngắn nhất từ
1 tới 2 và từ 1 tới 3, còn tuyến đường từ 1 tới 4 chỉ thuộc một
đường đi ngắn nhất từ 1 tới 4.
Yêu cầu: Cho n, m 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 107+7.
Dữ liệu: Vào từ file văn bản PATHS.INP:
 Dòng đầu tiên chứa 2 số nguyên n và m (1 ≤ n ≤ 1 500, 1
≤ m ≤ 5 000),
 Mỗi dòng trong m dòng sau chứa 3 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á 10 000).
Kết quả: Đưa ra file văn bản PATHS.OUT m dòng, mỗi dòng chứa một số nguyên, dòng thứ i
xác định kết quả tìm được với tuyến đường i.

Ví dụ

PATHS.INP                                 PATHS.OUT
                            4 4                                       2
                            1 2 5                                     3
                            2 3 5                                     2
                            3 4 5                                     1
                            1 4 8