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