We have focused our attention on shortest path problems where there is a single weight for each edge, and we need to find the shortest paths under these weights. In real life, often we have multiple criteria for determining good routes; for example, the cost of a route and the time taken. It turns out that many such problems are actually much harder than the standard shortest paths problems; but not all such problems are hard. You are given a directed graph G = (V, E) with weights on edges w : E R. A subset T of the vertices in V are marked as toll nodes. Design an algorithm that takes as input G, w, T, a source s, a destination t, and an integer k, and determines a path from s to t that contains at most k toll nodes and has shortest weight among all such paths. State the running time of your algorithm and prove it.