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

int main() {
    const int INF = 1e9;
    int n, src, dst, k;
    cin >> n >> src >> dst >> k;
    
    int m;
    cin >> m;
    // 邻接表：adj[u] 存储 (v, price)
    vector<vector<pair<int, int> > > adj(n);
    for (int i = 0; i < m; ++i) {
        int from, to, price;
        cin >> from >> to >> price;
        adj[from].push_back(make_pair(to, price));
    }
    
    // dist[u][s]：到节点u，用了s步的最短距离
    vector<vector<int> > dist(n, vector<int>(k + 2, INF));
    dist[src][0] = 0;
    
    // 优先队列：(距离, (节点, 步数))，用greater实现最小堆
    priority_queue<pair<int, pair<int, int> >,
                   vector<pair<int, pair<int, int> > >,
                   greater<pair<int, pair<int, int> > > > pq;
    pq.push(make_...