题解|大吉大利，晚上吃鸡！

    因为这道题目要求的是方案数，所以我们设一个两维数组f[i][x]作为从s(i==0)/t(i==1)到点x的最短路的条数。于是条件1就被转化为了：

    求两个点A和B，使得f[0][A]*f[1][A]+f[0][B]*f[1][B]=f[0][T](或者f[1][S])

    为了求出f数组，我们需要正反各跑一遍dijkstra，然后建出一个从S到T的最短路的图（显然这个图是一个DAG）。于是我们就满足了条件1。

    对于条件2的满足也很简单，我们只需要判断在这个最短路的DAG上，点A能否走到点B就可以了。

#include<cstdio>
#include<queue>
#include<map>
#include<cstring>
#include<bitset>
using namespace std;
inline void read(int &x,char ch=getchar(),bool f=0)
{
    for(x=0;ch>'9'||ch<'0';f=ch=='-',ch=getchar());
    for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
    (f)&&(x=-x);
}
const int N=5e4+5,M=5e4+5,mod=1e9+7;
int n,m,s,t;

//Part 1:Dijkstra
bool vis[N];
int f[2][N];
int head[M],cnt;
long long dis[2][N];
struct edge{
    int next,go,val;
}e[M<<1];
inline void add(int u,int v,int w){e[++cnt]=(edge){head[u],v,w},head[u]=cnt;}
struct data{
    int u;
    long long d;
    bool operator <(const data&a)const
    {
        return d>a.d;
    }
};
void dij(int s,int fx)
{
    memset(dis[fx],0x3f,sizeof(dis[fx]));
    dis[fx][s]=0,f[fx][s]=1;
    memset(vis,0,sizeof(vis));
    priority_queue<data> q;
    q.push((data){s,0});
    while(!q.empty())
    {
        data u=q.top();
        q.pop();
        if(vis[u.u])continue;
        vis[u.u]=1;
        for(int i=head[u.u];i;i=e[i].next)
        {
            int v=e[i].go;
            if(dis[fx][v]>dis[fx][u.u]+e[i].val)
            {
                dis[fx][v]=u.d+e[i].val;
                f[fx][v]=0;
                q.push((data){v,dis[fx][v]});
            }
            if(dis[fx][v]==dis[fx][u.u]+e[i].val)//如果有多条最短路，就把方案数累加
                f[fx][v]+=f[fx][u.u],f[fx][v]%=mod;//取模，不用管它
        }
    }
}
//Part 2:Topsort

//为了避免混淆，用namespace封***itset<N> from[N],to[N];
map<int,bitset<N> > uv;
int g[N];
namespace tp
{
    int head[N]={0},q[N]={0},in[N]={0},cnt=0;
    struct edge{
        int next,go;
    }e[M];
    inline void add(int u,int v){e[++cnt]=(edge){head[u],v},head[u]=cnt;}
    void topsort()//用拓扑处理出dp的顺序
    {
        for(int i=1,v;i<=cnt;i++)v=e[i].go,++in[v];
        int hea=0,tail=0;
        for(int i=1;i<=n;i++)
            if(in[i]==0)
                q[++tail]=i;
        while(tail<n)
        {
            int u=q[++hea];
            for(int i=head[u];i;i=e[i].next)
            {
                int v=e[i].go;
                --in[v];
                if(in[v]==0)q[++tail]=v;
            }
        }
    }
    long long solve()
    {
        long long ret=0;

        for(int i=1;i<=n;i++)//正向跑一遍
        {
            int uu=q[i];
            from[uu][uu]=1;
            for(int j=head[uu],vv;j;j=e[j].next)
            {
                vv=e[j].go;
                from[vv]|=from[uu];
            }
        }
        for(int i=n;i>=1;i--)//反向跑一遍
        {
            int uu=q[i];
            to[uu][uu]=1;
            for(int j=head[uu],vv;j;j=e[j].next)
            {
                vv=e[j].go;
                to[uu]|=to[vv];
            }
        }
        for(int i=1;i<=n;i++)//将答案累加
        {
            int uu=q[i];
            ret+=((~(from[uu]|to[uu]))&uv[(g[t]-g[uu]+mod)%mod]).count();
        }
        return ret>>1;//除2，避免重复
    }
}
int main()
{
    read(n),read(m),read(s),read(t);
    for(int i=1,u,v,w;i<=m;i++)
    {
        read(u),read(v),read(w);
        add(u,v,w),add(v,u,w);
    }
    dij(s,0);
    dij(t,1);
    if(f[0][t]==0)//注意判断不连通的情况（等价于f[1][s]==0）
    {
        printf("%lld",1ll*n*(n-1)>>1);//A可能情况*B可能情况/2（防止重复）
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[0][i]+dis[1][i]==dis[0][t])//如果这个点在从S到T的最短路上，就把它的方案数存起来
            g[i]=1ll*f[0][i]*f[1][i],g[i]%=mod;
        uv[g[i]][i]=1;//map存储
    }
    for(int i=1;i<=cnt;i+=2)//对于每一条合法的边，在新的图中加一条边
    {
        int v1=e[i].go,v2=e[i+1].go;
        if(dis[0][v1]+dis[1][v2]+e[i].val==dis[0][t])tp::add(v1,v2);
        if(dis[0][v2]+dis[1][v1]+e[i].val==dis[0][t])tp::add(v2,v1);
    }
    tp::topsort();//因为是DAG，所以可以用拓扑
    long long ans=tp::solve();//ans存储dp答案
    printf("%lld",ans);
    return 0;
}