Python/C++ 100% time
\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int n = passingFees.size();\n        
```\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int n = passingFees.size();\n        auto maxCost = accumulate(begin(passingFees), end(passingFees), 1);\n        \n        vector<vector<pair<int, int>>> g(n, vector<pair<int, int>>());\n        for (auto e: edges) {\n            g[e[1]].push_back({e[0], e[2]});\n            g[e[0]].push_back({e[1], e[2]});\n        }\n        \n        vector<int> minCostToDest(n, maxCost);\n        minCostToDest[n-1]=passingFees[n-1];\n        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;\n        pq.push({passingFees[n-1], n-1});\n        vector<array<int, 2>> parent(n, {-1, -1});\n        parent[n-1] = {n-1,0};\n        \n        while (pq.size() > 0) {\n            auto [curCost, curCity] = pq.top(); pq.pop();\n            if (curCost == minCostToDest[curCity]) {\n                for (auto [nxtCity, dTime]: g[curCity]) {\n                    auto nxtCost = curCost + passingFees[nxtCity];\n                    if (nxtCost < minCostToDest[nxtCity]) {\n                        parent[nxtCity] = {curCity, dTime};\n                        minCostToDest[nxtCity] = nxtCost;\n                        pq.push({nxtCost, nxtCity});\n                    }\n                }\n            }\n        }\n        \n        \n        if (parent[0][0] == -1) {\n            return -1;\n        }\n        int minCostTime = 0;\n        int curCity = 0;\n        while (curCity != n - 1) {\n            auto [nxtCity, dTime] = parent[curCity];\n            minCostTime += dTime;\n            curCity = nxtCity;\n        }\n        if (minCostTime <= maxTime) {\n            return minCostToDest[0];\n        }\n        \n        \n        vector<int> minTimeToDest(n, maxTime + 1);\n        pq.push({0, n - 1});\n        minTimeToDest[n-1] = 0;\n        while (pq.size() > 0) {\n            auto [curTime, curCity] = pq.top(); pq.pop();\n            if (curTime == minTimeToDest[curCity]) {\n                for (auto [nxtCity, dTime]: g[curCity]) {\n                    auto nxtTime = curTime + dTime;\n                    if (nxtTime < minTimeToDest[nxtCity]) {\n                        minTimeToDest[nxtCity] = nxtTime;\n                        pq.push({nxtTime, nxtCity});\n                    }\n                }\n            }\n        }\n        if (minTimeToDest[0] > maxTime) {\n            return -1;\n        }\n        \n        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq3;\n        pq3.push({0, 0, passingFees[0]});\n        int result = maxCost;\n        while (pq3.size() > 0) {\n            auto [curTime, curCity, curCost] = pq3.top(); pq3.pop();\n            if (curCost < result) {\n                if (curCity == n - 1) {\n                    result = curCost;\n                } else {\n                    for (auto [nxtCity, dTime]: g[curCity]) {\n                        if (curCost + minCostToDest[nxtCity] < result) {\n                            auto nxtTime = curTime + dTime;\n                            if (nxtTime + minTimeToDest[nxtCity] <= maxTime) {\n                                pq3.push({nxtTime, nxtCity, curCost + passingFees[nxtCity]});\n                            }\n                        }\n                    }\n                }\n            }\n        }\n        \n        \n        if (result < maxCost) {\n            return result;\n        } else {\n            return -1;\n        }\n    }\n};\n```\n```\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:\n        n = len(passingFees)\n        \n        maxCost = sum(passingFees) + 1\n        # build a dictionary\n        g = [[] for _ in range(n)]\n        for s, d, t in edges:\n            g[s].append((d, t))\n            g[d].append((s, t))\n            \n        # run Djikstra for minimal cost from every city to destination\n        minCostToDest = [maxCost] * n\n        pq = [(passingFees[-1], n - 1)]\n        parent = [(-1, -1)] * n\n        parent[-1] = n - 1\n        minCostToDest[-1] = passingFees[-1]\n        while pq:\n            curCost, curCity = heappop(pq)\n            if curCost == minCostToDest[curCity]:\n                for nxtCity, dTime in g[curCity]:\n                    nxtCost = curCost + passingFees[nxtCity]\n                    if nxtCost < minCostToDest[nxtCity]:\n                        parent[nxtCity] = (curCity, dTime)\n                        minCostToDest[nxtCity] = nxtCost\n                        heappush(pq, (nxtCost, nxtCity))\n        # no path to destination from 0\n        if parent[0][0] == -1:\n            return -1\n        minCostTime = 0\n        curCity = 0\n        # check if the min cost path is coming under the maxTime, this is our result then\n        while curCity != n - 1:\n            curCity, dTime = parent[curCity]\n            minCostTime += dTime\n        if minCostTime <= maxTime:\n            return minCostToDest[0]\n        \n        # run Djikstra for the min time to n - 1 for every city\n        minTimeToDest = [maxTime + 1] * n\n        pq.append((0, n - 1))\n        minTimeToDest[-1] = 0\n        while pq:\n            curTime, curCity = heappop(pq)\n            if curTime == minTimeToDest[curCity]:\n                for nxtCity, dTime in g[curCity]:\n                    nxtTime = curTime + dTime\n                    if nxtTime < minTimeToDest[nxtCity]:\n                        minTimeToDest[nxtCity] = nxtTime\n                        heappush(pq, (nxtTime, nxtCity))\n\n        # check if the min time is coming over limit, no solution if it is\n        if minTimeToDest[0] > maxTime:\n            return -1\n        \n        # now run "unbound Djikstra"\n        # check every possible path, only cut those that are either overtime or over the found solution\n        pq.append((0, 0, passingFees[0]))\n        result = maxCost\n        while pq:\n            curTime, curCity, curCost = heappop(pq)\n            if curCost < result:\n                if curCity == n - 1:\n                    result = curCost\n                else:\n                    for nxtCity, dTime in g[curCity]:\n                        if curCost + minCostToDest[nxtCity] < result:\n                            nxtTime = curTime + dTime\n                            if nxtTime + minTimeToDest[nxtCity] <= maxTime:\n                                heappush(pq, (nxtTime, nxtCity, curCost + passingFees[nxtCity]))\n        if result < maxCost:\n            return result\n        else:\n            return -1\n```
[]