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

#define  ll long long
#define ld long double
#define f first
#define s second
const int N = 30;

int n , m , s , t , s2 , t2;
ll ds[N][N];
vector< pair<int,int> > adj[N];
vector<int> adj2[N];

void dijk(int st)
{
    for(int i=0; i<=n; i++)
        ds[st][i] = 1e18;

    ds[st][st] = 0;
    priority_queue< pair<ll,ll> , vector< pair<ll,ll> > , greater< pair<ll,ll> > > q;
    q.push({0 , st});
    while(!q.empty())
    {
        int node = q.top().s;
        ll cst = q.top().f;
        q.pop();

        if (cst > ds[st][node]) continue;

        for(auto ch : adj[node])
        {
            ll cst2 = cst + ch.s;

            if (cst2 < ds[st][ch.f])
            {
                ds[st][ch.f] = cst2;
                q.push({ds[st][ch.f] , ch.f});
            }
        }
    }
}

ll cnt = 0;

vector<int> all_masks;
void dfs(int node , int msk , int sink)
{
    cnt++;
    if (node == sink)
    {
        all_masks.push_back(msk);
        return;
    }

    for(auto ch : adj2[node])
    {
        dfs(ch , msk | (1<<ch) , sink);
    }
}

void nadaf(vector<int> masks , vector<int> &maskNdeef , int b)
{
    for(auto it : masks)
    {
        int c = 0 , newMsk = 0;
        for(int i=0; i<n; i++)
        {
            if ( ((1<<i)&it) && !b && (i == s2 || i == t2) ) goto here;
            if ( ((1<<i)&it) && b && (i == s || i == t) ) goto here;

            if (i == s || i == t || i == s2 || i == t2) continue; //msh 3ayzo
            if ((1<<i) & it)
            {
                newMsk |= (1<<c);
            }
            c++;
        }
        maskNdeef.push_back(newMsk);

        here:
        continue;
    }
}

ll brute(vector<int> masks , vector<int> masks2)
{
    ll ans = 0;
    for(auto it : masks)
    {
        for(auto it2 : masks2)
        {
            if (it&it2) continue;
            ans++;
        }
    }
    return ans;
}

void prnt(vector<int> masks)
{
    for(auto it : masks)
        cout << it << ' ';
    cout << "\n";
}

ll dp[1<<22];

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x , y , c;
        cin >> x >> y >> c;
        x-- , y--;
        adj[x].push_back({y , c});
        adj[y].push_back({x , c});
    }

    for(int i=0; i<n; i++)
        dijk(i);

    cin >> s >> t >> s2 >> t2;
    s-- , t-- , s2-- , t2--;

    for(int i=0; i<n ;i++)
    {
        for(auto it : adj[i])
        {
            int v = i , u = it.f , cst = it.s;
            if (ds[s][v] + cst + ds[u][t] == ds[s][t])
            {
                adj2[v].push_back(u);
            }
        }
    }

    vector<int> masks , masks2; //masks of path 1 and path 2
    vector<int> maskNdeef , maskNdeef2;

    dfs(s , 1<<s , t);
    masks = all_masks;

    all_masks.clear();
    for(int i=0; i<n; i++)
        adj2[i].clear();

    for(int i=0; i<n ;i++)
    {
        for(auto it : adj[i])
        {
            int v = i , u = it.f , cst = it.s;
            if (ds[s2][v] + cst + ds[u][t2] == ds[s2][t2])
            {
                adj2[v].push_back(u);
            }
        }
    }
    dfs(s2 , 1<<s2 , t2);
    masks2 = all_masks;

    ll ans = 0;
   // cout << brute(masks , masks2) << "\n";

    //prnt(masks);
    //prnt(masks2);

    nadaf(masks , maskNdeef , 0);
    nadaf(masks2 , maskNdeef2 , 1);

    int mx = (1<<21) - 1;
    for(auto &it : maskNdeef)
    {
        it ^= (mx);
    }
    for(auto it : maskNdeef2)
    {
        dp[it]++;
    }

    for(int i=1; i<=mx; i <<= 1)
    {
        for(int j=0; j<=mx; j++)
        {
            if ((i&j))
            {
                dp[j] += dp[i^j];
            }
        }
    }

    for(auto it : maskNdeef)
    {
        ans += dp[it];
    }
    cout << ans << "\n";


    return 0;
}