#include <bits/stdc++.h> using namespace std; using ll = long long; #define vi vector<long long> #define pr pair<ll, ll> const ll INF = 2e15; // Set safely above K (10^15) to prevent overflow during addition void dij(int n, int start, vi &dist, const vector<vector<pr>>& adj) { dist.assign(n + 1, INF); priority_queue<pr, vector<pr>, greater<pr>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto& edge : adj[u]) { if (dist[u] + edge.second < dist[edge.first]) { dist[edge.first] = dist[u] + edge.second; pq.push({dist[edge.first], edge.first}); } } } } void solution() { int n, m; if (!(cin >> n >> m)) return; ll S, T, L, K; cin >> S >> T >> L >> K; vector<vector<pr>> adj(n + 1); for (int i = 0; i < m; i++) { int u, v; ll c; cin >> u >> v >> c; adj[u].push_back({v, c}); adj[v].push_back({u, c}); } vi dS, dT; dij(n, S, dS, adj); dij(n, T, dT, adj); // Case: King is already happy with existing lines if (dS[T] <= K) { cout << (ll)n * (n - 1) / 2 << endl; // All possible ways [cite: 13] return; } ll ans = 0; // Standard O(N^2) loop to check all pairs {u, v} [cite: 13] for (int u = 1; u <= n; u++) { for (int v = u + 1; v <= n; v++) { // New path can go S -> u -> v -> T OR S -> v -> u -> T ll pathA = dS[u] + L + dT[v]; ll pathB = dS[v] + L + dT[u]; if (pathA <= K || pathB <= K) { ans++; } } } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solution(); return 0; }