#include iostream#include vector#include algorithm#include cstringusing namespace std;const int INF = 2147483647;int n e source destination m;vectorpairint int graph1005;int dp10051005;void dfsint u i

#include #include #include #include using namespace std;

const int INF = 2147483647; int n, e, source, destination, m; vector<pair<int, int>> graph[1005]; int dp[1005][1005];

void dfs(int u, int cnt) { if (cnt > m) return; if (dp[u][cnt] != INF) return; if (u == destination && cnt == m) { dp[u][cnt] = 0; return; } for (auto v : graph[u]) { dfs(v.first, cnt + 1); dp[u][cnt] = min(dp[u][cnt], dp[v.first][cnt + 1] + v.second); } }

int main() { cin >> n >> e; for (int i = 0; i < e; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); } memset(dp, INF, sizeof(dp)); cin >> source >> destination >> m; dfs(source, 0); if (dp[source][0] == INF) cout << 2147483647 << endl; else cout << dp[source][0] << endl; return 0; }