find all paths from source to destinations and then calculate the path with minimum cost I am trying to solve one problem. Please refer complete problem statement before proceeding.

You are given a road network, with N cities and M bi-directional
roads. Each road has some positive amount of tax associated to
it,meaning if there is a road connecting cities A and B with tax C,
you will need to pay C rupees to the government every time when you
use this road.
but you have a wildcard which can be used at most K times and when you
use wildcard while using a road, you do not need to pay tax associated
with the road.
You are planning to visit one city this weekend, due to limited budged
you want to estimate minimum passible cost from you home-city to every
other city, so that you can choose the destination according to the
budget, your home-city is a city numbered with 1.

For solving above problem I am Following this approach. Step 1) Calculate all the path between vertices u,v. Step 2) For a Path p=[i-j-k-l] do following
   for(int i=0;i&lt;k;i++){
           int weight=findEdgeWithMaxWeight(p);
     cost of path p=cost of path-weight;
    }

I am repeating this step2 for all the paths for u,v and at last I am choosing the path with minimum weight. As my answer.
Consider following diagram to visualize my approach.

But problem with above approach is that I am have to calulate all the path between u,v to get the answer. Is there any way to get the optimal path with out calculating all the paths?
Edit: Hope Problem is bit clearer now.
One way to solve this is a Dijkstra variant with the following DP-Relaxation:
The distance array will be 2-dimensional array for which $Dist[i][j]$ is the shortest path from the source to the city $i$ using $j$ wildcards.
When processing a vertex $i$, for an incident edge $e\{i, j\}$ with cost $c$ we update as following:(for all values of k)
$Dist[j][k] = min(Dist[j][k], Dist[i][k] + C)$ 
$Dist[j][k] = min(Dist[j][k], Dist[i][k-1])$
The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $K$ factor in the relaxation i.e. $O((e+n\log(n))k)$ using Fibonacci Heaps.