cf-95C

/* We can do all pair shortest path by O(n*n*logn) instead of O(n*n*n) by running dijkstra n times . */

int n,m,sor,des;vector<pii> v[MAX],v2[MAX];ll t[MAX],w[MAX],c[MAX];ll dis[MAX];

void dij(int s)
{
    for(int i = 1;i<=n;i++)dis[i] = 1e15;
    dis[s] = 0;

    priority_queue<pii ,vector<pii> ,greater <pii> >pq;

    pq.push(pii(dis[s],s));

    while(!pq.empty())
    {
        pii x = pq.top();
        pq.pop();
        for(auto it : v[x.ss])
        {
            if(dis[it.ss]>dis[x.ss]+it.ff)
            {
                dis[it.ss] = dis[x.ss] + it.ff;
                pq.push(pii(dis[it.ss],it.ss));
            }
        }
    }

    for(int i = 1;i<=n;i++)
    {
        if(i==s)continue;
        if(dis[i]<=t[s])
        {
            v2[s].pb(pii(w[s],i));

        }
    }
}

ll dij2(int s)
{
    for(int i = 1;i<=n;i++)dis[i] = 1e15;
    dis[s] = 0;

    priority_queue<pii ,vector<pii> ,greater <pii> >pq;
    pq.push(pii(dis[s],s));

    while(!pq.empty())
    {
        pii x = pq.top();
        pq.pop();
        for(auto it : v2[x.ss])
        {
            if(dis[it.ss]>dis[x.ss]+it.ff)
            {
                dis[it.ss] = dis[x.ss] + it.ff;
                pq.push(pii(dis[it.ss],it.ss));
            }
        }
    }
    if(dis[des]<1e15)return dis[des];
    else return -1 ;
}


int main()
{
    booster()
    ///read("input.txt");
    cin>>n>>m>>sor>>des;

    for(int i = 0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb(pii(c,b));
        v[b].pb(pii(c,a));
    }

    for(int i = 0;i<n;i++)
    {
        cin>>t[i+1]>>w[i+1];
    }


    for(int i = 1;i<=n;i++)
    {
        dij(i);
    }

    cout<<dij2(sor);



    return 0;
}