13713

#include <iostream>
#include <limits.h>
using namespace std;

int flag[10003][10003];
int arr[10003][10003];

int main() {
    int N, E;
    int s, f, k;
    int u, v;
    int w;
    

    cin >> N >> E;
    cin >> s >> f >> k;
    for (int i = 0; i < 10003; i++) {
        for (int j = 0; j < 10003; j++) {
            arr[i][j] = INT_MAX;
        }
    }

    for (int i = 0; i < E; i++) {
        cin >> u >> v >> w;
        arr[u][v] = w;
    }

    
    for (int j = 0; j < N; j++) {
        flag[0][j] = arr[s][j];
    }

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < N; j++) {
            flag[i][j] = flag[i-1][j];
            for (int k = 0; k < N; k++) {
                if (flag[i-1][k] + arr[k][j] < flag[i][j] && flag[i-1][k] != INT_MAX && arr[k][j] != INT_MAX) {
                    flag[i][j] = flag[i-1][k] + arr[k][j];
                }
            }
        }
    }
    
    int min = flag[0][f];

    for (int i = 1; i <= k; i++) {
        if (flag[i][f] < min) min = flag[i][f];
    }


    if (min >= INT_MAX) cout << "-1\n";
    else cout << min << endl;

    return 0;


    
}