#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>

using namespace std;
typedef long long ll;

struct Edge;
struct Node{
	ll cost;
	bool isClosed;
	vector<Edge*> edges;
	Node* last;
	
	Node(){}
};

struct NODE{
	Node* node;
	ll costWhenPushed;
	bool operator<(const NODE& rhs) const { return costWhenPushed > rhs.costWhenPushed; } // 逆にする
	NODE(Node* n, ll cost){
		node = n;
		costWhenPushed = cost;
	}
};

struct Edge{
	Node* node0;
	Node* node1;
	ll cost;
};

vector<Node> Nodes;
vector<Edge> Edges;

ll Dijkstra_Find(Node* s, Node* g){
	// 初期化
	for(int i = 0; i < Nodes.size(); i++){
		Nodes[i].cost = &Nodes[i] == s ? 0 : LLONG_MAX / 2;
		Nodes[i].isClosed = false;
		Nodes[i].last = nullptr;
	}
	priority_queue<NODE> que;
	que.push(NODE(s, 0));
	
	while(!que.empty()){
		Node* n = que.top().node;
		ll costWhenPushed = que.top().costWhenPushed;
		que.pop();
		if(n->cost < costWhenPushed){
			continue;
		}
		n->isClosed = true;
		
		int size = (n->edges).size();
		for(int i = 0; i < size; i++){
			Node* processNode = (n->edges)[i]->node0 == n ? (n->edges)[i]->node1 : (n->edges)[i]->node0;
			if(processNode->isClosed){
				continue;
			}
			
			ll newCost = n->cost + (n->edges)[i]->cost;
			if( newCost < processNode->cost ){
				processNode->cost = newCost;
				processNode->last = n;
				que.push(NODE(processNode, newCost));
			}
		}
	}
	
	return g->cost;
}

int main()
{
	for(int i = 0; i < 1000000; i++){
		Node node;
		Edge edge;
		Nodes.push_back(node);
		Edges.push_back(edge);
	}
	
	ll N, M, S;
	ll U[100];
	ll V[100];
	ll A[100];
	ll B[100];
	ll C[50];
	ll D[50];
	
	cin >> N >> M >> S;
	for(int i = 0; i < M; i++){
		cin >> U[i] >> V[i] >> A[i] >> B[i];
	}
	for(int i = 0; i < N; i++){
		cin >> C[i] >> D[i];
	}
	
	int edgeCount = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 2499; j++){
			int id0 = 2500 * i + j;
			int id1 = 2500 * i + (j + C[i]);
			if(j + C[i] >= 2500){
				id1 = 2500 * i + 2499;
			}
			{
				Edge* edge = &Edges[edgeCount];
				edgeCount++;
				Node* node0 = &Nodes[id0];
				Node* node1 = &Nodes[id1];
				
				edge->cost = D[i];
				edge->node0 = node0;
				edge->node1 = node1;
				node0->edges.push_back(edge);
				// node1->edges.push_back(edge);
			}
		}
	}
	
	for(int i = 0; i < M; i++){
		for(int j = 0; j < 2500; j++){
			if(j - A[i] < 0 ){ continue; }
			{
				int id0 = 2500 * (U[i]-1) + j;
				int id1 = 2500 * (V[i]-1) + j - A[i];
			
				Edge* edge = &Edges[edgeCount];
				edgeCount++;
				Node* node0 = &Nodes[id0];
				Node* node1 = &Nodes[id1];
			
				edge->cost = B[i];
				edge->node0 = node0;
				edge->node1 = node1;
				node0->edges.push_back(edge);
				// node1->edges.push_back(edge);
			}
			
			{
				int id0 = 2500 * (V[i]-1) + j;
				int id1 = 2500 * (U[i]-1) + j - A[i];
			
				Edge* edge = &Edges[edgeCount];
				edgeCount++;
				Node* node0 = &Nodes[id0];
				Node* node1 = &Nodes[id1];
			
				edge->cost = B[i];
				edge->node0 = node0;
				edge->node1 = node1;
				node0->edges.push_back(edge);
				// node1->edges.push_back(edge);
			}
		}
	}
	
	Dijkstra_Find(&Nodes[S < 2500 ? S : 2499], &Nodes[(N-1)*2500]);
	for(int i = 1; i < N; i++){
		ll cost = LLONG_MAX;
		for(int j = 0; j < 2500; j++){
			if(Nodes[i*2500 + j].cost < cost){
				cost = Nodes[i*2500 + j].cost;
			}
		}
		cout << cost << endl;
	}
	
	return 0;
}


Measured memory_bytes: 98028