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ố.

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 ~10^9 + 7~.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ (~1 \le n \le 1500, 1 \le m \le 5000~).
• 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á 10000).

Output

• Ghi ra ~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~.

Sample Input 1

4 4
1 2 5
2 3 5
3 4 5
1 4 8

Sample Output 1

3
2
1
1