Mạng lưới giao thông của một quốc gia gồm ~N~ thành phố và ~M~ con đường một chiều. Các thành phố được đánh số từ ~1~ đến ~N~.

Đối với mỗi đường, ta biết:

• Thành phố xuất phát

• Thành phố đích

• Độ dài của con đường

Ta nói rằng đường ~F~ là sự tiếp nối của đường ~E~ nếu thành phố đích của ~E~ trùng với thành phố xuất phát của ~F~.

Một đường đi (path) từ thành phố ~A~ đến thành phố ~B~ là một dãy các con đường thỏa mãn:

• Thành phố xuất phát của con đường đầu tiên là ~A~

• Mỗi con đường tiếp theo là sự tiếp nối của con đường trước đó

• Thành phố đích của con đường cuối cùng là ~B~

Độ dài của đường đi được tính bằng tổng độ dài của tất cả con đường trong đường đi đó. Một đường đi ngắn nhất từ ~A~ đến ~B~ là đường đi mà không tồn tại đường đi nào khác từ ~A~ đến ~B~ có tổng độ dài nhỏ hơn.

Yêu cầu: Đối với mỗi đường, hãy xác định có bao nhiêu đường đi ngắn nhất khác nhau chứa con đường đó. Vì kết quả có thể rất lớn, hãy in kết quả khi chia dư cho ~10^9+7~.

Input

- Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 1500~, ~1 \le M \le 5*10^3~).

- ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~U~, ~V~ và ~W~. Chúng đại diện cho một con đường một chiều từ thành phố ~U~ đến thành phố ~V~ có độ dài ~W~ (~U \neq V~, ~1 \le U,V \le N~, ~W \le 10^4~).

Output

In ~M~ số nguyên, mỗi số trên một dòng, trong đó:

+ Số thứ ~i~ là số lượng đường đi ngắn nhất khác nhau có chứa con đường thứ ~i~.

+ Kết quả lấy modulo ~10^9+7~.

+ Thứ tự kết quả phải trùng với thứ tự con đường trong dữ liệu vào.

Scoring

- ~30\%~ số điểm tương ứng với ~n \le 15~, ~W \le 30~.

- ~60\%~ số điểm tương ứng với ~n \le 300~, ~W \le 10^3~.

- ~10\%~ số điểm không có ràng buộc gì thêm.

Sample Input 1

4 3
1 2 5
2 3 5
3 4 5

Sample Output 1

3
4
3

Notes

Có ~4~ thành phố và ~3~ con đường:

Đồ thị thực chất là một chuỗi tuyến tính:

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~

Ta xét mọi cặp thành phố ~(A,B)~ sao cho tồn tại đường đi từ ~A~ đến ~B~.

Các cặp thành phố có đường đi:

Tổng cộng ~6~ đường đi ngắn nhất.

Đếm số đường đi ngắn nhất chứa từng cạnh

Cạnh 1 (~1 \rightarrow 2~) - Các đường đi chứa cạnh này:

~1 \rightarrow 2~

~1 \rightarrow 2 \rightarrow 3~

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~

~\rightarrow~ Có ~3~ đường.

~\Rightarrow~ Output dòng ~1 = 3~.

Cạnh 2 (~2 \rightarrow 3~) ta làm tương tự.