Number of shortest paths - MarisaOJ: Marisa Online Judge

Number of shortest paths

Time limit: 1000 ms
Memory limit: 256 MB
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 109+7. ### Constraints - 1≤n,m≤2×105. - 1≤u,v≤n. - 1≤w≤109. ### Example Input: 33121232133 Output: 2