Given an undirected, weighted graph of $n$ vertices and $m$ edges. Find the number of shortest paths from $1$ to $n$.
### Input
- The first line contains 2 integers $n, m$.
- The next $m$ lines, each line contains 3 integers $u, v, w$, there is an edge of weight $w$ connecting $u, v$ .
### Output
- Print the number of shortest paths from $1$ to $n$, modulo $10^9+7$.
### Constraints
- $1 \le n, m \le 2 \times 10^5$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
### Example
Input:
```
3 3
1 2 1
2 3 2
1 3 3
```
Output:
```
2
```
