我的参考题解：https://www.cnblogs.com/ccz181078/p/7907022.html；
不过我感觉题解的压位有问题，（1<<x）还不炸上天。不过这题数据水，好像怎么写都能对，这里放上我认为正确的写法
//正经解法是计算一个F(x)表示经过x的最短路条数，然后找F(A)+F(B)=F(T),用map来做。
//而且F(x)可能很大，还要取模，一个不够的话可能还要取两个。
//而网上的这种随机算法相比之下就显得很简洁了（但由于这题数据很弱好像这部分写错也可以过）
//关于这种做法的正确性，显然所有的最短路都经过的点的f值为0
//那么为什么靠两个f值相同且非0且不能在树形图中互达的点能将图分成两个部分呢，我们可以考虑用一个点将两部分连起来
//这样这个点的f值为0，也就是说它能到所有点，那把它去掉图当然被分成两个部分。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
const int N=5e4+;
int n,m,pp,cp,fa[N],S,T,last[N],pre[N*],other[N*],w[N*],t;
void add(int x,int y,int z){
++t;pre[t]=last[x];last[x]=t;other[t]=y;w[t]=z;
}
struct node{
int id;
i64 dis;
bool operator<(const node&a)const{
return dis>a.dis;
}
}A,B;
priority_queue<node>q;
bool vis[N];
i64 dis[N],ans=;
u64 f[N];
u32 can[N][N/+];
int _get(u32*a,int x){return (a[x>>]>>(x&))&;}
void _set(u32*a,int x){a[x>>]|=<<(x&);}
void _or(u32*a,u32*b){
int p=n/+;
for(int i=;i<=p;i+=){
a[i]|=b[i];a[i+]|=b[i+];
a[i+]|=b[i+];a[i+]|=b[i+];
}
}
void f1(int x){//从T往回找最短路图，我觉得和从S开始找是一样的。
vis[x]=;
for(int i=last[x];i;i=pre[i]){
int v=other[i];
if(dis[v]+w[i]==dis[x]){
if(!vis[v])fa[v]=x,f1(v);
else{
u64 z=rand();
z=z<<^rand();
f[x]^=z;f[fa[v]]^=z;
}
}
}
}
struct hehe{
int id;
u64 v,dis;
bool operator<(const hehe&a)const{
return v!=a.v?v<a.v:dis>a.dis;
}
}tmp[N];
void f2(int x){
_set(can[x],x);
vis[x]=;
for(int i=last[x];i;i=pre[i]){
int v=other[i];
if(dis[v]+w[i]==dis[x]){
if(vis[v])f2(v),f[x]^=f[v];
_or(can[x],can[v]);
}
}
if(f[x])tmp[pp++]=(hehe){x,f[x],dis[x]};
else ++cp;
}
void calc(){
f1(T);f2(T);
sort(tmp,tmp+pp);
for(int i=,j=;i<pp;i=j){
int t=;
for(++j;j<pp&&tmp[i].v==tmp[j].v;++j)t+=_get(can[tmp[i].id],tmp[j].id);
//图一定可以分成两个部分，一部分是经过A的最短路，一部分是经过B的，两部分没有交集。
ans+=i64(j-i-t)*t;//因为f值相同的是按dis值排序的，所以此时的f一定是按A,B分的两个集合中的一个。
}
ans+=cp*i64(n-cp-pp);
printf("%lld\n",ans);
//system("pause");
}
bool dijkstra(){
for(int i=;i<=n;++i)dis[i]=1ll<<;
A.id=S;A.dis=;dis[S]=;q.push(A);
while(!q.empty()){
B=q.top();q.pop();
if(B.dis!=dis[B.id])continue;
if(B.id==T){calc();return ;}
for(int i=last[B.id];i;i=pre[i]){
int v=other[i];
if(dis[v]>dis[B.id]+w[i]){
dis[v]=dis[B.id]+w[i];
A.id=v;A.dis=dis[v];q.push(A);
}
}
}
return ;
}
int main(){
int x,y,z;
cin>>n>>m>>S>>T;
srand(n^m^T^S^);
for(int i=;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
if(!dijkstra())printf("%lld\n",n*i64(n-)/);
//system("pause");
return ;
}