Easy top down DP + Memoization
\nclass Solution {\npublic:\n    unordered_map<int,vector<pair<int,int>>> adj;\n    int dp[1002][1002];\n    int go(int sum,vector<int> &cost,int src=0)\n    {\
```\nclass Solution {\npublic:\n    unordered_map<int,vector<pair<int,int>>> adj;\n    int dp[1002][1002];\n    int go(int sum,vector<int> &cost,int src=0)\n    {\n        if(sum<0)\n            return INT_MAX-1000;\n        if(src==cost.size()-1)\n            return sum>=0?0:INT_MAX-1000;\n        if(dp[sum][src]!=-1)\n            return dp[sum][src];\n        int res=INT_MAX-1000;\n        for(auto i:adj[src])\n        {\n            res=min(res,cost[src]+go(sum-i.second,cost,i.first));\n        }\n        return dp[sum][src]=res;\n    }\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& cost) \n    {\n        memset(dp,-1,sizeof(dp));\n        adj.clear();\n          for(auto i:edges)\n          {\n              adj[i[0]].push_back({i[1],i[2]});\n              adj[i[1]].push_back({i[0],i[2]});\n          }\n        int ans=go(maxTime,cost);\n        if(ans==2147482647)\n            return -1;\n        return cost[size(cost)-1]+ans;\n    }\n};\n```
['Dynamic Programming', 'Memoization']