Untitled

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

//vector<int> vec[10000];
int len[10000][10000] ={0};
int vec[10000][10000] = {0};
int q[10000] = {0};
//int shortest_path(int n, int path, int s, int e){
//    int p;
//    if(s == e)
//        return path;
//    for (int i = 0; i < v[s].size(); i++) {
//        p = v[s][i] + shortest_path(n-1, path + v[s][i], i, e);
//    }
//
//}
int shortest = 2147483647;
int path = 0;
int k;


void find(int n, int start, int end){
    if(start == end){
        if(path < shortest){
            shortest = path;
//            path = 0;
            return;
        }
    }
    if(n == k+1) {
//        path = 0;
        return;
    }
    else{
//        if(vec[start].empty()) return;
//        for(int i = 0; i < vec[start].size(); i++){
//            path += len[start][vec[start][i]];
//            find(n+1, vec[start][i], end);
//            path -= len[start][vec[start][i]];
//        }
        if(q[start] == 0) return;
        for(int i = 0; i < q[start]; i++){
            path += len[start][vec[start][i]];
            find(n+1, vec[start][i], end);
            path -= len[start][vec[start][i]];
        }
    }
    
}


int main() {
    int N, E;
    int s, f;
    int u, v, w;
    cin >> N >> E;
    cin >> s >> f >> k;
    for(int i = 0; i < E; i++){
        cin >> u >> v >> w;
        len[u][v] = w;
//        vec[u].push_back(v);
        vec[u][q[u]] = v;
        q[u]++;
    }
    find(0, s, f);
    if(shortest == 2147483647) cout << -1 << endl;
    else cout << shortest << endl;
    return 0;
}