Cho một đồ thị vô hướng, có trọng số gồm \(n\) đỉnh và \(m\) cạnh. Tìm số lượng đường đi ngắn nhất từ \(1\) đến \(n\).

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(u,v,w\), có cạnh trọng số \(w\) nối \(u,v\).

Output

• In ra số lượng đường đi ngắn nhất từ \(1\) đến \(n\), modulo \(10^9+7\)..

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le w \le 10^9\)

Sample Input 1

3 3
1 2 1
2 3 2
1 3 3

Sample Output 1

2