#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int dijkstra(int num, vector<pair<int, int>> *route, int *start, int *goal, vector<int> *bestroute = NULL, long long *costmap = NULL)
{
    long long *cost = costmap;
    if( costmap == NULL ) cost = (long long*) malloc(  sizeof(long long) * num );
    int *parent = (int*) malloc( sizeof(int) * num );
    bool *isgoal = (bool*)malloc( sizeof(bool) * num );
    for( int i = 0; i < num; i++ ) 
    {
        cost[i] = ( ((long long)1)<< 62 );
        parent[i] = -1;
        isgoal[i] = false;
    }
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> q;
    for( int *s = start; *s >= 0; s++ ) 
    {
        cost[*s] = 0;
        q.push(make_pair(0, *s));
    }
    if( goal != NULL )
    {
        for( int *g = goal; *g >= 0; g++ ) isgoal[*g] = true;
    }
    while( !q.empty() )
    {
        pair<long long,int> n = q.top();
        q.pop();
        if( n.first > cost[n.second] ) continue;
        cost[n.second] = n.first;
        if( isgoal[n.second] )
        {
            if (bestroute != NULL)
            {
                int k = n.second;
                do
                {
                   bestroute->push_back(k);
                   k = parent[k];
                } while (k >= 0);                
            }
            if(costmap == NULL) free(cost);
            free(parent);
            free(isgoal);            
            return n.first;
        }
        for( int i = 0; i < route[n.second].size(); i++ )
        {
            int k = route[n.second][i].first;
            if( n.first + route[n.second][i].second < cost[k] )
            {
                cost[k] = n.first + route[n.second][i].second;
                parent[k] = n.second;
                q.push(make_pair(cost[k], k));
            }
        }
    }

    if(costmap == NULL) free(cost);
    free(parent);
    free(isgoal);
    return -1;
}


int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    vector<pair<int, int>> *route = new vector<pair<int, int>>[n * 50 * n];
    int amax = 0;
    for( int i = 0; i < m; i++ )
    {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        amax = max(amax, a);
        for( int c = a; c < 50 * n; c++ ) 
        {
            route[ u + c * n ].push_back(make_pair(v + (c - a) * n, b));
            route[ v + c * n ].push_back(make_pair(u + (c - a) * n, b));
        }
    }

    int moneymax = amax * (n - 1);
    
    for( int i = 0; i < n; i++ )
    {
        int c, d;
        cin >> c >> d;
        for( int k = 0; k <= moneymax; k++ )
        {
            route[ i + k * n ].push_back(make_pair(i + n * min(k + c, moneymax), d));
        }
    }

    int *start = new int[2];
    int *goal = new int[moneymax + 1];
    if( s > moneymax ) s = moneymax;
    start[0] = (s * n);
    start[1] = -1; 
    long long *cost = (long long*) malloc(  sizeof(long long) * n * (moneymax + 1) );

    dijkstra(n * (moneymax + 1), route, start, NULL, NULL, cost) ;
    for( int t = 1; t < n; t++)
    {
        long long mincost = cost[t];
        for(int c = 1; c < moneymax + 1; c++) mincost = min(mincost, cost[t + c * n]);
        cout << mincost << endl;         
    }  
}


Measured memory_bytes: 18216