# Cheapest Flights Within K Stops
## Problem Statement
You are given $n$ cities, indexed from $0$ to $n-1$. There are a number of flights connecting these cities. Each flight is represented as a tuple $(u_i, v_i, \text{price}_i)$, indicating a direct flight from city $u_i$ to city $v_i$ with a cost of $\text{price}_i$.
Your task is to find the cheapest price to travel from a given source city $\text{src}$ to a destination city $\text{dst}$, with at most $k$ stops. A stop refers to an intermediate city where you land and then take another flight. For example, a path with $L$ flights has $L-1$ stops. If there is no such route with at most $k$ stops, return $-1$.
## Input Format
- First line: a single integer $n$ ($1 \le n \le 10^5$), the number of cities.
- Second line: a single integer $m$ ($0 \le m \le 10^5$), the number of flights.
- The next $m$ lines each contain three integers $u_i, v_i, \text{price}_i$ ($0 \le u_i, v_i < n$, $u_i \ne v_i$, $1 \le \text{price}_i \le 10^4$), describing the $i$-th flight.
- The last line contains three integers $\text{src}, \text{dst}, k$ ($0 \le \text{src}, \text{dst} < n$, $\text{src} \ne \text{dst}$, $0 \le k < n$), representing the source city, destination city, and the maximum number of stops allowed.
## Output Format
Print a single integer, the minimum cost to travel from $\text{src}$ to $\text{dst}$ with at most $k$ stops. If no such route exists, print $-1$.
## Sample Test Cases
### Sample Input 1
```
4
5
0 1 100
1 2 100
2 0 100
1 3 600
2 3 200
0 3 1
```
### Sample Output 1
```
700
```
### Sample Input 2
```
3
3
0 1 100
1 2 100
0 2 500
0 2 1
```
### Sample Output 2
```
200
```
### Sample Input 3
```
3
3
0 1 100
1 2 100
0 2 500
0 2 0
```
### Sample Output 3
```
500
```
## Constraints
- $1 \le n \le 10^5$
- $0 \le m \le 10^5$
- For each flight $(u_i, v_i, \text{price}_i)$:
- $0 \le u_i, v_i < n$
- $u_i \ne v_i$
- $1 \le \text{price}_i \le 10^4$
- There will not be any multiple flights between the same two cities.
- $0 \le \text{src}, \text{dst} < n$
- $\text{src} \ne \text{dst}$
- $0 \le k < n$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1:
- Cities: $n=4$. Flights connect cities $0, 1, 2, 3$.
- Source: $\text{src}=0$, Destination: $\text{dst}=3$, Max stops: $k=1$.
- Path $0 \to 1 \to 3$: This path consists of two flights $0 \to 1$ and $1 \to 3$. The total cost is $100 + 600 = 700$. It has $1$ stop (city $1$), which is $\le k$.
- Path $0 \to 1 \to 2 \to 3$: This path consists of three flights. The total cost is $100 + 100 + 200 = 400$. It has $2$ stops (cities $1, 2$), which is $> k$. Thus, this path is invalid.
- The cheapest valid path is $0 \to 1 \to 3$ with cost $700$.
### Sample 2:
- Cities: $n=3$. Flights connect cities $0, 1, 2$.
- Source: $\text{src}=0$, Destination: $\text{dst}=2$, Max stops: $k=1$.
- Path $0 \to 1 \to 2$: Cost $100 + 100 = 200$. This path has $1$ stop (city $1$), which is $\le k$.
- Path $0 \to 2$: Cost $500$. This path has $0$ stops, which is $\le k$.
- The cheapest valid path is $0 \to 1 \to 2$ with cost $200$.
### Sample 3:
- Cities: $n=3$. Flights connect cities $0, 1, 2$.
- Source: $\text{src}=0$, Destination: $\text{dst}=2$, Max stops: $k=0$.
- Path $0 \to 1 \to 2$: Cost $100 + 100 = 200$. This path has $1$ stop, which is $> k$. Thus, this path is invalid.
- Path $0 \to 2$: Cost $500$. This path has $0$ stops, which is $\le k$.
- The cheapest valid path is $0 \to 2$ with cost $500$.
Loading problem statement...