#include <iostream>
#include <vector>
using namespace std;

int main() {
    const int INF = 1e9;
    int n, src, dst, k;
    cin >> n >> src >> dst >> k;
    
    int m;
    cin >> m;
    vector<vector<int> > flights;
    for (int i = 0; i < m; ++i) {
        int from, to, price;
        cin >> from >> to >> price;
        vector<int> flight;
        flight.push_back(from);
        flight.push_back(to);
        flight.push_back(price);
        flights.push_back(flight);
    }
    
    // prev_dist[i] 表示上一轮（s-1条边）到i的最短距离
    vector<int> prev_dist(n, INF);
    prev_dist[src] = 0;
    
    // 迭代k+1次，对应最多k+1条边（k次中转）
    for (int i = 0; i <= k; ++i) {
        vector<int> curr_dist = prev_dist; // 初始继承上一轮结果
        for (int j = 0; j < flights.size(); ++j) {
            int from = flights[j][0];
            int to = flights[j][1];
            int price = fli...