#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
const int INF = 1000000;
void PrintGraph(std::vector<std::vector<std::pair<int, int>>> graph) {
for (int i = 0; i < graph.size(); ++i) {
std::cout << i << " : ";
for (int j = 0; j < graph[i].size(); ++j) {
std::cout << graph[i][j].first << " : w = " << graph[i][j].second << ", ";
}
std::cout << "\n";
}
}
std::vector<std::vector<std::pair<int, int>>> ReverseGraph(std::vector<std::vector<std::pair<int, int>>> graph) {
std::vector<std::vector<std::pair<int, int>>> graphR(graph.size());
for (int i = 0; i < graph.size(); ++i) {
for (int j = 0; j < graph[i].size(); ++j) {
graphR[graph[i][j].first].push_back(std::make_pair(i, graph[i][j].second));
}
}
return graphR;
}
void InitializeSingleSource(int source, std::vector<int> &distances, std::vector<int> &parents) {
for (int i = 0; i < distances.size(); ++i) {
distances[i] = INF;
parents[i] = -1;
}
distances[source] = 0;
}
void Relax(int u, int v, int weight,
std::set<std::pair<int, int>> &q,
std::vector<int> &distances, std::vector<int> &parents) {
if (distances[v] > distances[u] + weight) {
q.erase(std::make_pair(distances[v], v));
distances[v] = distances[u] + weight;
parents[v] = u;
q.insert(std::make_pair(distances[v], v));
}
}
void Dijkstra(std::vector<std::vector<std::pair<int, int>>> graph,
std::vector<int> &distances, std::vector<int> &parents,
int source) {
InitializeSingleSource(source, distances, parents);
std::set<std::pair<int, int>> q;
for (int i = 0; i < graph.size(); ++i) {
q.insert(std::make_pair(distances[i], i));
}
int u, v;
int weight;
while (!q.empty()) {
u = q.begin()->second;
q.erase(q.begin());
// if (forwardDistances[uF] + backwardDistances[uB] >= Dmin) {
// break;
// }
for (int i = 0; i < graph[u].size(); ++i) {
v = graph[u][i].first;
weight = graph[u][i].second;
// if (distances[v] > distances[u] + weight) {
// q.erase(std::make_pair(distances[v], v));
// distances[v] = distances[u] + weight;
// parents[v] = u;
// q.insert(std::make_pair(distances[v], v));
// }
Relax(u, v, weight, q, distances, parents);
}
}
}
struct ComparatorAsc {
std::vector<int> values;
bool operator() (int i,int j) {
return (values[i] < values[j]);
}
};
struct ComparatorDesc {
std::vector<int> values;
bool operator() (int i,int j) {
return (values[i] > values[j]);
}
};
int main() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<std::vector<std::pair<int, int>>> graphR(n);
std::vector<int> forwardDistances(n);
std::vector<int> backwardDistances(n);
std::vector<int> forwardParents(n);
std::vector<int> backwardParents(n);
int u, v, weight;
for (int i = 0; i < m; ++i) {
std::cin >> u >> v >> weight;
graph[u - 1].push_back(std::make_pair(v - 1, weight));
}
int s, t, d;
std::cin >> s >> t >> d;
Dijkstra(graph, forwardDistances, forwardParents, s - 1);
graphR = ReverseGraph(graph);
Dijkstra(graphR, backwardDistances, backwardParents, t - 1);
std::vector<int> forwardIndices(n);
std::vector<int> backwardIndices(n);
for (int i = 0; i < n; ++i) {
forwardIndices[i] = i;
backwardIndices[i] = i;
}
long long count = 0;
if (forwardDistances[t - 1] <= d) {
count = n*(n - 1);
} else {
ComparatorAsc forwardCompare;
ComparatorDesc backwardCompare;
forwardCompare.values = forwardDistances;
backwardCompare.values = backwardDistances;
std::sort(forwardIndices.begin(), forwardIndices.end(), forwardCompare);
std::sort(backwardIndices.begin(), backwardIndices.end(), backwardCompare);
int j = 0;
for (int i = 0; i < n; ++i) {
while ((forwardDistances[forwardIndices[i]] + backwardDistances[backwardIndices[j]] >= d) && (j < n)) {
j += 1;
}
count += n - j;
}
}
std::cout << count << "\n";
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKY29uc3QgaW50IElORiA9IDEwMDAwMDA7Cgp2b2lkIFByaW50R3JhcGgoc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4+IGdyYXBoKSB7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGdyYXBoLnNpemUoKTsgKytpKSB7CiAgICAgICAgc3RkOjpjb3V0IDw8IGkgPDwgIiA6ICI7CiAgICAgICAgZm9yIChpbnQgIGogPSAwOyBqIDwgZ3JhcGhbaV0uc2l6ZSgpOyArK2opIHsKICAgICAgICAgICAgc3RkOjpjb3V0IDw8IGdyYXBoW2ldW2pdLmZpcnN0IDw8ICIgOiB3ID0gIiA8PCBncmFwaFtpXVtqXS5zZWNvbmQgPDwgIiwgIjsKICAgICAgICB9CiAgICAgICAgc3RkOjpjb3V0IDw8ICJcbiI7CiAgICB9Cn0KCnN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+PiBSZXZlcnNlR3JhcGgoc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4+IGdyYXBoKSB7CiAgICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+Pj4gZ3JhcGhSKGdyYXBoLnNpemUoKSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGdyYXBoLnNpemUoKTsgKytpKSB7CiAgICAgICAgZm9yIChpbnQgIGogPSAwOyBqIDwgZ3JhcGhbaV0uc2l6ZSgpOyArK2opIHsKICAgICAgICAgICAgZ3JhcGhSW2dyYXBoW2ldW2pdLmZpcnN0XS5wdXNoX2JhY2soc3RkOjptYWtlX3BhaXIoaSwgZ3JhcGhbaV1bal0uc2Vjb25kKSk7CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiBncmFwaFI7Cn0KCnZvaWQgSW5pdGlhbGl6ZVNpbmdsZVNvdXJjZShpbnQgc291cmNlLCBzdGQ6OnZlY3RvcjxpbnQ+ICZkaXN0YW5jZXMsIHN0ZDo6dmVjdG9yPGludD4gJnBhcmVudHMpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZGlzdGFuY2VzLnNpemUoKTsgKytpKSB7CiAgICAgICAgZGlzdGFuY2VzW2ldID0gSU5GOwogICAgICAgIHBhcmVudHNbaV0gPSAtMTsKICAgIH0KICAgIGRpc3RhbmNlc1tzb3VyY2VdID0gMDsKfQoKdm9pZCBSZWxheChpbnQgdSwgaW50IHYsIGludCB3ZWlnaHQsCiAgICAgICAgICAgc3RkOjpzZXQ8c3RkOjpwYWlyPGludCwgaW50Pj4gJnEsCiAgICAgICAgICAgc3RkOjp2ZWN0b3I8aW50PiAmZGlzdGFuY2VzLCBzdGQ6OnZlY3RvcjxpbnQ+ICZwYXJlbnRzKSB7CiAgICBpZiAoZGlzdGFuY2VzW3ZdID4gZGlzdGFuY2VzW3VdICsgd2VpZ2h0KSB7CiAgICAgICAgcS5lcmFzZShzdGQ6Om1ha2VfcGFpcihkaXN0YW5jZXNbdl0sIHYpKTsKCQlkaXN0YW5jZXNbdl0gPSBkaXN0YW5jZXNbdV0gKyB3ZWlnaHQ7CgkJcGFyZW50c1t2XSA9IHU7CgkJcS5pbnNlcnQoc3RkOjptYWtlX3BhaXIoZGlzdGFuY2VzW3ZdLCB2KSk7CiAgICB9Cn0KCnZvaWQgRGlqa3N0cmEoc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4+IGdyYXBoLAogICAgICAgICAgICAgIHN0ZDo6dmVjdG9yPGludD4gJmRpc3RhbmNlcywgc3RkOjp2ZWN0b3I8aW50PiAmcGFyZW50cywKICAgICAgICAgICAgICBpbnQgc291cmNlKSB7CiAgICBJbml0aWFsaXplU2luZ2xlU291cmNlKHNvdXJjZSwgZGlzdGFuY2VzLCBwYXJlbnRzKTsKCiAgICBzdGQ6OnNldDxzdGQ6OnBhaXI8aW50LCBpbnQ+PiBxOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBncmFwaC5zaXplKCk7ICsraSkgewogICAgICAgIHEuaW5zZXJ0KHN0ZDo6bWFrZV9wYWlyKGRpc3RhbmNlc1tpXSwgaSkpOwogICAgfQoKICAgIGludCB1LCB2OwogICAgaW50IHdlaWdodDsKICAgIHdoaWxlICghcS5lbXB0eSgpKSB7CiAgICAgICAgdSA9IHEuYmVnaW4oKS0+c2Vjb25kOwoJCXEuZXJhc2UocS5iZWdpbigpKTsKCiAgICAgICAgLy8gaWYgKGZvcndhcmREaXN0YW5jZXNbdUZdICsgYmFja3dhcmREaXN0YW5jZXNbdUJdID49IERtaW4pIHsKICAgICAgICAvLyAgICAgYnJlYWs7CiAgICAgICAgLy8gfQoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGdyYXBoW3VdLnNpemUoKTsgKytpKSB7CiAgICAgICAgICAgIHYgPSBncmFwaFt1XVtpXS5maXJzdDsKICAgICAgICAgICAgd2VpZ2h0ID0gZ3JhcGhbdV1baV0uc2Vjb25kOwoJCQkvLyBpZiAoZGlzdGFuY2VzW3ZdID4gZGlzdGFuY2VzW3VdICsgd2VpZ2h0KSB7CgkJCS8vIAlxLmVyYXNlKHN0ZDo6bWFrZV9wYWlyKGRpc3RhbmNlc1t2XSwgdikpOwoJCQkvLyAJZGlzdGFuY2VzW3ZdID0gZGlzdGFuY2VzW3VdICsgd2VpZ2h0OwoJCQkvLyAJcGFyZW50c1t2XSA9IHU7CgkJCS8vIAlxLmluc2VydChzdGQ6Om1ha2VfcGFpcihkaXN0YW5jZXNbdl0sIHYpKTsKICAgICAgICAgICAgLy8gfQogICAgICAgICAgICBSZWxheCh1LCB2LCB3ZWlnaHQsIHEsIGRpc3RhbmNlcywgcGFyZW50cyk7CgkJfQogICAgfQp9CgpzdHJ1Y3QgQ29tcGFyYXRvckFzYyB7CglzdGQ6OnZlY3RvcjxpbnQ+IHZhbHVlczsKICAgIGJvb2wgb3BlcmF0b3IoKSAoaW50IGksaW50IGopIHsgCgkgICAgcmV0dXJuICh2YWx1ZXNbaV0gPCB2YWx1ZXNbal0pOwogICAgfQp9OwoKc3RydWN0IENvbXBhcmF0b3JEZXNjIHsKCXN0ZDo6dmVjdG9yPGludD4gdmFsdWVzOwogICAgYm9vbCBvcGVyYXRvcigpIChpbnQgaSxpbnQgaikgeyAKCSAgICByZXR1cm4gKHZhbHVlc1tpXSA+IHZhbHVlc1tqXSk7CiAgICB9Cn07CgoKaW50IG1haW4oKSB7CiAgICBpbnQgbiwgbTsKICAgIHN0ZDo6Y2luID4+IG4gPj4gbTsKCiAgICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+Pj4gZ3JhcGgobik7CiAgICBzdGQ6OnZlY3RvcjxzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+Pj4gZ3JhcGhSKG4pOwogICAgc3RkOjp2ZWN0b3I8aW50PiBmb3J3YXJkRGlzdGFuY2VzKG4pOwogICAgc3RkOjp2ZWN0b3I8aW50PiBiYWNrd2FyZERpc3RhbmNlcyhuKTsKICAgIHN0ZDo6dmVjdG9yPGludD4gZm9yd2FyZFBhcmVudHMobik7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IGJhY2t3YXJkUGFyZW50cyhuKTsKCiAgICBpbnQgdSwgdiwgd2VpZ2h0OwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyArK2kpIHsKICAgICAgICBzdGQ6OmNpbiA+PiB1ID4+IHYgPj4gd2VpZ2h0OwogICAgICAgIGdyYXBoW3UgLSAxXS5wdXNoX2JhY2soc3RkOjptYWtlX3BhaXIodiAtIDEsIHdlaWdodCkpOwogICAgfQoKICAgIGludCBzLCB0LCBkOwogICAgc3RkOjpjaW4gPj4gcyA+PiB0ID4+IGQ7CgogICAgRGlqa3N0cmEoZ3JhcGgsIGZvcndhcmREaXN0YW5jZXMsIGZvcndhcmRQYXJlbnRzLCBzIC0gMSk7CiAgICBncmFwaFIgPSBSZXZlcnNlR3JhcGgoZ3JhcGgpOwogICAgRGlqa3N0cmEoZ3JhcGhSLCBiYWNrd2FyZERpc3RhbmNlcywgYmFja3dhcmRQYXJlbnRzLCB0IC0gMSk7CgogICAgc3RkOjp2ZWN0b3I8aW50PiBmb3J3YXJkSW5kaWNlcyhuKTsKICAgIHN0ZDo6dmVjdG9yPGludD4gYmFja3dhcmRJbmRpY2VzKG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBmb3J3YXJkSW5kaWNlc1tpXSA9IGk7CiAgICAgICAgYmFja3dhcmRJbmRpY2VzW2ldID0gaTsKICAgIH0KCiAgICBsb25nIGxvbmcgY291bnQgPSAwOwogICAgaWYgKGZvcndhcmREaXN0YW5jZXNbdCAtIDFdIDw9IGQpIHsKICAgICAgICBjb3VudCA9IG4qKG4gLSAxKTsKICAgIH0gZWxzZSB7CiAgICAgICAgQ29tcGFyYXRvckFzYyBmb3J3YXJkQ29tcGFyZTsKICAgICAgICBDb21wYXJhdG9yRGVzYyBiYWNrd2FyZENvbXBhcmU7CiAgICAgICAgZm9yd2FyZENvbXBhcmUudmFsdWVzID0gZm9yd2FyZERpc3RhbmNlczsKICAgICAgICBiYWNrd2FyZENvbXBhcmUudmFsdWVzID0gYmFja3dhcmREaXN0YW5jZXM7CiAgICAgICAgc3RkOjpzb3J0KGZvcndhcmRJbmRpY2VzLmJlZ2luKCksIGZvcndhcmRJbmRpY2VzLmVuZCgpLCBmb3J3YXJkQ29tcGFyZSk7CiAgICAgICAgc3RkOjpzb3J0KGJhY2t3YXJkSW5kaWNlcy5iZWdpbigpLCBiYWNrd2FyZEluZGljZXMuZW5kKCksIGJhY2t3YXJkQ29tcGFyZSk7CiAgICAKICAgICAgICBpbnQgaiA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICAgICAgd2hpbGUgKChmb3J3YXJkRGlzdGFuY2VzW2ZvcndhcmRJbmRpY2VzW2ldXSArIGJhY2t3YXJkRGlzdGFuY2VzW2JhY2t3YXJkSW5kaWNlc1tqXV0gPj0gZCkgJiYgKGogPCBuKSkgeyAKICAgICAgICAgICAgICAgIGogKz0gMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBjb3VudCArPSBuIC0gajsKICAgICAgICB9CiAgICB9CiAgICBzdGQ6OmNvdXQgPDwgY291bnQgPDwgIlxuIjsKICAgIHJldHVybiAwOwp9Cg==