#include <bits/stdc++.h> #pragma GCC optimize("O3") // #define int long long #define ll long long #define se second #define fi first #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; typedef pair<ll,int> pii; typedef pair<pii,pii> ipii; const int MAXN = 5e5+100; const int MAXA = 2e5+10; const int SQRT = 450; const ll INF = 1e18; const int MOD = 998244353; const int LOG = 30; int sum(int a, int b){ int te = a+MOD+b; for(; te >= MOD; ) te -= MOD; return te; } void chsum(int &a, int b){ a = sum(a,b); } int mul(int a, int b){ return a*b%MOD; } void chmul(int &a, int b){ a = mul(a,b); } void chmn(auto &a, auto b){ a = min(a, b); } void chmx(auto &a, auto b){ a = max(a, b); } int expo(int a, int b){ if(b==0) return 1; int te = expo(a, b/2); te = mul(te,te); // temporary -> te return (b%2 ? mul(te, a) : te); } ll n, m, s,t,l,k; ll dis[MAXN], dis2[MAXN]; vector<pii> adj[MAXN]; priority_queue <pii, vector<pii>, greater<pii>> pq; void dji(int sta){ for(int i=1; i<=n; i++) dis[i] = INF; dis[sta] = 0; pq.push({0, sta}); while(!pq.empty()){ auto [x, nw] = pq.top(); pq.pop(); if(dis[nw] > x) continue; for(auto [nx, wei] : adj[nw]){ if(dis[nx] > x+wei){ dis[nx] = x+wei; pq.push({dis[nx], nx}); } } } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; cin>>s>>t>>l>>k; for(int i=1; i<=m; i++){ int x, y, w; cin>>x>>y>>w; adj[x].pb({y, w}); adj[y].pb({x, w}); } dji(t); for(int i=1; i<=n; i++) dis2[i] = dis[i]; dji(s); if(dis[t] <= k){ cout << 1ll*n*(n-1)/2 << '\n'; exit(0); } k -= l; ll ans = 0; for(int i=1; i<=n; i++) if(dis[i]+dis2[i] <= k) ans--; sort(dis2+1, dis2+n+1); sort(dis+1, dis+n+1); int las = n; for(int i=1; i<=n; i++){ // itung yg memenuhi ini while(las>=1 && dis[i]+dis2[las] > k) las--; ans += las; // if(te<=k-dis[i]) ans++; } cout << ans << '\n'; }