#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 3005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int ans;
int h[maxn],head=1;
struct yyy {
	int to,z,w;
	void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn];
int d1[maxn],d2[maxn],N;
int s1,t1,s2,t2;
void spfa(int s,int *dis) {
	int i;
	queue<int>q;
	q.push(s);dis[s]=0;
	while (!q.empty()) {
		int x=q.front();q.pop();
		for (i=h[x];i;i=a[i].z) if (dis[a[i].to]>dis[x]+a[i].w) {
			dis[a[i].to]=dis[x]+a[i].w;
			q.push(a[i].to);
		}
	}
}
int vis[maxn],f[(1<<20)+5],id[maxn],tot;
void dfs1(int x,int stat) {
	int i;
	if (x==t1) return ++tot,f[stat]++,void();
	for (i=h[x];i;i=a[i].z) 
		if (d1[a[i].to]==d1[x]+a[i].w&&vis[a[i].to]!=2) {
			if (!vis[a[i].to]) dfs1(a[i].to,stat|(1<<id[a[i].to]));
			else dfs1(a[i].to,stat);
		}
} 
void dfs2(int x,int stat) {
	int i;
	if (x==t2) {
		ans+=f[(N-1)^stat];
//		gdb(stat,f[(N-1)^stat],ans);
		return ;
	}
	for (i=h[x];i;i=a[i].z) 
		if (d2[a[i].to]==d2[x]+a[i].w&&vis[a[i].to]!=1) {
			if (!vis[a[i].to]) dfs2(a[i].to,stat|(1<<id[a[i].to]));
			else dfs2(a[i].to,stat);
		}
}
signed main(void){
	int i,j,x,y,z;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(x),read(y);read(z);
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	}
	read(s1),read(t1),read(s2),read(t2);
	memset(d1,0x3f,sizeof(d1));
	memset(d2,0x3f,sizeof(d2));
	vis[s1]=vis[t1]=1;vis[s2]=vis[t2]=2;
	spfa(s1,d1);
	spfa(s2,d2);
	int times=0;
	for (i=1;i<=n;i++) if (vis[i]==0) id[i]=times++; 
	dfs1(s1,0);
	N=(1<<n-4);
//	for (i=0;i<N;i++) gdb(i,f[i]);
	for (j=0;j<n-4;j++) {
		for (i=0;i<N;i++) if ((i>>j)&1) {
			f[i]+=f[i^(1<<j)];
		}
	}
//	for (i=0;i<N;i++) gdb(i,f[i]);
	
	dfs2(s2,0);
//	if (n==24) printf("%d\n",tot);
	printf("%d\n",ans);
	return 0;
}