Cho đồ thị có hướng, có trọng số gồm $n$ đỉnh và $m$ cạnh. Một đường đi đơn giữa hai đỉnh được gọi là ngắn nhất nếu không tồn tại đường đi nào khác giữa hai đỉnh đó có tổng trọng số các cạnh thuộc đường đi nhỏ hơn.

Với mỗi cạnh, hãy đếm số lượng đường đi ngắn nhất giữa hai đỉnh bất kì và đi qua nó. Hai đường đi được gọi là khác nhau nếu dãy các cạnh đi qua của chúng khác nhau. Có thể không tồn tại đường đi giữa hai đỉnh bất kì.

Dữ liệu vào

• Dòng đầu tiên là số nguyên $n,m$ ~(1 \leq n \leq 1500, 1 \leq m \leq 5000)~.
• $m$ dòng tiếp, dòng thứ $i$ gồm ba số nguyên ~u_i,v_u,w_i~, thể hiện một cạnh có hướng từ ~u_i~ sang ~v_i~ có trọng số ~w_i~ ~(1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10000)~.

Dữ liệu ra

• In ra $m$ dòng, dòng thứ $i$ là số lượng đường đi ngắn nhất đi qua cạnh thứ $i$ modulo $10^9+7$.

Ví dụ

Đầu vào

4 4
1 2 2
1 4 3
3 4 2
2 3 2

Đầu ra

2
1
2
3

Subtask

• Subtask ~1~ ~(20\%~ số điểm~)~: Đảm bảo đồ thị không có chu trình.
• Subtask ~2~ ~(10\%~ số điểm~)~ : $n,m \le 10$.
• Subtask ~3~ ~(20\%~ số điểm~)~: $n,m \le 100$.
• Subtask ~4~ ~(50\%~ số điểm~)~: Không có ràng buộc gì thêm.