#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using pii = pair<int, int>;

#define fi           first
#define se           second
#define All(x)       x.begin(), x.end()
#define debug(x)     cout << #x << " = " << (x) << '\n';
#define debugV(v, x) cout << #v << "[" << (x) << "] = " << v[x] << '\n';

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
    return os << "(" << p.fi << ", " << p.se << ")";
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
    os << "{"; bool osu = 1;
    for (auto i : v) {if (!osu) {os << ", ";} os << i; osu = 0;}
    return os << "}";
}

const int iINF = 1'000'000'000;
const ll INF   = 1'000'000'000'000'000'000;

const int maxN  = 24;
const int maxM  = 1 << 20;

int N, M, K;
vector<pii> adj[maxN];
int msk[2][maxM];
bool in[maxN];
int id[maxN];
int s[2], t[2];

void Dijkstra(int st, vector<int> &dist) {
    vector<bool> vis(N, false);
    priority_queue<pii, vector<pii>, greater<pii>> pyqe;
    pyqe.push({0, st});
    dist[st] = 0;
    while (!pyqe.empty()) {
        auto [cdist, cur] = pyqe.top();
        pyqe.pop();
        if (vis[cur]) continue;

        vis[cur] = true;
        for (auto [nxt, w] : adj[cur]) {
            if (dist[nxt] > dist[cur] + w) {
                dist[nxt] = dist[cur] + w;
                pyqe.push({dist[nxt], nxt});
            }
        }
    }
}

void calc(int x) {
    array<vector<int>, 2> dist = {};
    dist[0] = dist[1] = vector<int>(N, iINF);
    
    Dijkstra(s[x], dist[0]);
    Dijkstra(t[x], dist[1]);

    // debugV(dist, 0); debugV(dist, 1);

    vector<vector<int>> dag(N);
    vector<int> deg(N, 0);
    for (int cur = 0; cur < N; cur++) {
        for (auto [nxt, w] : adj[cur]) {
            if (dist[0][cur] + w + dist[1][nxt] == dist[0][t[x]]) {
                dag[cur].push_back(nxt);
                deg[nxt]++;
            }
        }
    }
    // for (int cur = 0; cur < N; cur++) debugV(dag, cur);

    vector<vector<int>> pth(N);
    queue<int> Q;

    Q.push(s[x]);
    pth[s[x]] = {0};
    vector<bool> vis2(N, false);

    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        if (vis2[cur]) continue;

        vis2[cur] = true;

        for (auto nxt : dag[cur]) {
            if ((nxt != s[x ^ 1]) && (nxt != t[x ^ 1])) {
                if (in[nxt]) {
                    for (auto p : pth[cur]) pth[nxt].push_back(p | (1 << id[nxt]));
                } else {
                    for (auto p : pth[cur]) pth[nxt].push_back(p);
                }
            }
            deg[nxt]--;
            if (!deg[nxt]) Q.push(nxt);
        }

        if (cur != t[x]) pth[cur].clear();
    }

    // debugV(pth, t[x]);
    // debug(pth[t[x]].size());
    for (auto p : pth[t[x]]) msk[x][p] = 1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> K;
    for (int u, v, w, i = 1; i <= K; i++) {
        cin >> u >> v >> w;
        u--, v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cin >> s[0] >> t[0] >> s[1] >> t[1];
    s[0]--, t[0]--, s[1]--, t[1]--;
    
    for (int i = 0; i < N; i++) in[i] = true;
    in[s[0]] = in[t[0]] = in[s[1]] = in[t[1]] = false;

    for (int t = 0, i = 0; i < N; i++) {
        if (!in[i]) continue;
        id[i] = t++;
    }

    for (int i = 0; i <= 1; i++) calc(i);

    // SOS
    int M = 1 << (N-4);
    int MX = M - 1;
    for (int i = 0; i < N-4; i++) {
        for (int m = 0; m < M; m++) {
            if (m & (1 << i)) msk[0][m] += msk[0][m ^ (1 << i)];
        }
    }

    ll ans = 0;
    for (int m = 0; m < M; m++) {
        if (msk[1][m]) {
            // debugV(msk[0], MX ^ m);
            ans = ans + (ll)msk[0][MX ^ m];
        }
    }
    cout << ans << '\n';
}