JOI Rail Network Expansion

JOI country has \(N\) train stations, numbered from \(1\) to \(N\), and \(M\) bidirectional railway lines. For each \(i\ (1 \le i \le M)\), the line connects station \(A_i\) and station \(B_i\) with a travel time of \(C_i\) minutes.

The Minister decides to add a new railway line between two distinct stations \(u\) and \(v\) (with \(1 \le u < v \le N\)). This new line connects station \(u\) and station \(v\) with a travel time of \(L\) minutes (even if there already exists a line between the two stations). If after adding this new railway line, it is possible to travel from station \(S\) to station \(T\) in at most \(K\) minutes (we do not consider transfer or waiting times), then the King will be pleased.

Determine the number of choices of \(u, v\) (from the total \(\frac{N(N-1)}{2}\) possibilities) that will make the King happy.

The shortest travel time after adding the new line can be computed as:

[ \min\big( d(S,T),; d(S,u)+L+d(v,T),; d(S,v)+L+d(u,T) \big) \le K, ]

where \(d(x,y)\) is the shortest travel time from station \(x\) to station \(y\) in the original network.

inputFormat

The first line contains six integers \(N\), \(M\), \(L\), \(S\), \(T\), and \(K\). \(N\) is the number of stations, \(M\) is the number of railway lines, \(L\) is the travel time of the new line, \(S\) and \(T\) are the start and destination stations, and \(K\) is the maximum allowed travel time for the King to be happy.

Each of the following \(M\) lines contains three integers \(A_i\), \(B_i\), and \(C_i\) describing a railway line between stations \(A_i\) and \(B_i\) with travel time \(C_i\) minutes.

outputFormat

Output a single integer representing the number of two-station choices \((u, v)\) that will make the King happy.

sample

3 2 3 1 3 6
1 2 3
2 3 3

3