#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int INF = 1e9;

int main() {
    int n, src, dst, k;
    cin >> n >> src >> dst >> k;
    int m;
    cin >> m;
    
    vector<vector<int> > flights(m, vector<int>(3));
    for (int i = 0; i < m; ++i) {
        cin >> flights[i][0] >> flights[i][1] >> flights[i][2];
    }
    
    // dp[stops][city] = 经过 stops 次航班到达 city 的最低价格
    // stops 取值范围 0 到 k+1
    vector<vector<int> > dp(k + 2, vector<int>(n, INF));
    dp[0][src] = 0;
    
    for (int stops = 1; stops <= k + 1; ++stops) {
        // 先复制上一轮的结果（也可不复制，但为了取最小值时保留未更新的城市）
        // 实际上 dp[stops] 初始为 INF，我们只需用上一轮更新即可
        for (int i = 0; i < m; ++i) {
            int u = flights[i][0];
            int v = flights[i][1];
            int w = flights[i][2];
            if (d...