Задача

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define f first
#define s second
#define mp make_pair
int n,m,st,fn;
double k,d[100000],xx[100000],yy[100000];
bool u[100000];
vector<pair<int,double> > a[100000]; 

double Calc(double T,int v)
{
                         
    if (v == fn) return T;
    double W = xx[v] + yy[v];
    long long x = (long long)floor(T/W);
    while (x*W < T) x++;

    x--;

    if (x*W + xx[v] >= T) return T;
    
    return x*W + W;
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    
    scanf("%d%d%lf",&n,&m,&k);
    for (int i = 0; i < m; i++) {                                     
        int l,r;
        double w;
        scanf("%d%d%lf",&l,&r,&w);
        a[l].push_back(mp(r,w));
        a[r].push_back(mp(l,w));
    }

    for (int i = 1; i <= n; i++) scanf("%lf%lf",&xx[i],&yy[i]);

    scanf("%d%d",&st,&fn);
    
    double inf = (1ll<<59);
    for (int i = 1; i <= n; i++) d[i] = inf;
    d[st] = 0;
    
    while (true) {
        int pos = -1;
        for (int i = 1; i <= n; i++)
        if (!u[i] && (pos == -1 || d[pos] > d[i])) pos = i;

        if (pos == -1 || d[pos] == inf) break;

        u[pos] = true;

        for (int i = 0; i < a[pos].size(); i++) {
            int to = a[pos][i].f;
            double w = a[pos][i].s;

            d[to] = min(d[to],Calc(d[pos]+w*k,to));
        }
    }

    if (d[fn] == inf) puts("-1"); else
    printf("%.4lf",d[fn]);
    return 0;
}