Number of Ways to Arrive at Destination
Code


# Code
```python []
class Solution(object):
    def countPaths(self, n, roads):
        """
        :type n: int
        :type roads: List[List[int]]
        :rtype: int
        """
        MOD, graph = 10**9 + 7, {i: [] for i in range(n)}
        for u, v, t in roads:
            graph[u].append((v, t))
            graph[v].append((u, t))

        dist, ways = [float('inf')] * n, [0] * n
        dist[0], ways[0], heap = 0, 1, [(0, 0)]

        while heap:
            d, node = heapq.heappop(heap)
            if d > dist[node]: continue
            for nei, t in graph[node]:
                new_dist = d + t
                if new_dist < dist[nei]:
                    dist[nei], ways[nei] = new_dist, ways[node]
                    heapq.heappush(heap, (new_dist, nei))
                elif new_dist == dist[nei]:
                    ways[nei] = (ways[nei] + ways[node]) % MOD

        return ways[n - 1]

```
['Python']