int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> adjList(n);
        for (auto it : roads) {
            adjList[it[0]].push_back({it[1], it[2]});
            adjList[it[1]].push_back({it[0], it[2]});
        }
        priority_queue<
            pair<long long, long long>,
            vector<pair<long long, long long>>,
            greater<pair<long, long>>
        > pq;
        pq.push({0, 0});

        int shortestTime = INT_MAX;
        int shortestPaths = 0;
        int mod = 1e9 + 7;

        vector<long long> dist(n,1e18);
        dist[0] = 0;

        while(!pq.empty()) {
            auto top = pq.top();
            pq.pop();

            if(top.second == n-1) {
                if(shortestTime > top.first) {
                    shortestTime = top.first;
                    shortestPaths = 1;
                } else if (shortestTime == top.first) {
                    shortestPaths++;
                    shortestPaths = shortestPaths % mod;
                }
            }

            for(auto& it: adjList[top.second]) {
                long long distance = top.first + it.second;
                if(distance <= dist[it.first]) {
                    pq.push({distance, it.first});
                    dist[it.first] = distance;
                }
            }
        }

        return shortestPaths;
    }