package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	m := scanInt()
	s := scanInt()

	g := make([][]train, n)

	for i := 0; i < m; i++ {
		u := scanInt() - 1
		v := scanInt() - 1
		a := scanInt()
		b := scanInt()
		g[u] = append(g[u], train{v, a, b})
		g[v] = append(g[v], train{u, a, b})
	}

	c := make([]int, n)
	d := make([]int, n)
	for i := 0; i < n; i++ {
		c[i] = scanInt()
		d[i] = scanInt()
	}

	vn := n * 3000
	dist := make([]int, vn)
	for i := 0; i < vn; i++ {
		dist[i] = inf
	}
	s = min(s, 2500)
	dist[s] = 0
	pq := &pqForDijkstra{vert{0, s}}
	heap.Init(pq)

	ans := make([]int, n)
	for i := 0; i < n; i++ {
		ans[i] = inf
	}

	for len(*pq) != 0 {
		p := heap.Pop(pq).(vert)
		if p.d > dist[p.v] {
			continue
		}
		v := p.v / 3000
		co := p.v % 3000
		cost := dist[p.v] + d[v]
		to := min(2500, co+c[v]) + v*3000
		if cost < dist[to] {
			dist[to] = cost
			heap.Push(pq, vert{dist[to], to})
		}
		for _, e := range g[v] {
			if e.a > co {
				continue
			}
			cost = dist[p.v] + e.b
			to = co - e.a + e.to*3000
			if cost < dist[to] {
				dist[to] = cost
				ans[e.to] = min(ans[e.to], dist[to])
				heap.Push(pq, vert{dist[to], to})
			}
		}
	}

	for i := 1; i < n; i++ {
		fmt.Fprintln(wr, ans[i])
	}

}

type train struct{ to, a, b int }

const inf = 1<<60 - 1

type edge struct{ to, co int }
type vert struct{ d, v int }
type pqForDijkstra []vert

func (pq pqForDijkstra) Len() int            { return len(pq) }
func (pq pqForDijkstra) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq pqForDijkstra) Less(i, j int) bool  { return pq[i].d < pq[j].d }
func (pq *pqForDijkstra) Push(x interface{}) { *pq = append(*pq, x.(vert)) }
func (pq *pqForDijkstra) Pop() interface{} {
	x := (*pq)[len(*pq)-1]
	*pq = (*pq)[0 : len(*pq)-1]
	return x
}

func dijkstra(es [][]edge, s int) []int {
	d := make([]int, len(es))
	for i := 0; i < len(es); i++ {
		d[i] = inf
	}
	d[s] = 0
	pq := &pqForDijkstra{vert{0, s}}
	heap.Init(pq)
	for len(*pq) != 0 {
		p := heap.Pop(pq).(vert)
		if p.d > d[p.v] {
			continue
		}
		for _, e := range es[p.v] {
			cost := d[p.v] + e.co
			if cost < d[e.to] {
				d[e.to] = cost
				heap.Push(pq, vert{d[e.to], e.to})
			}
		}
	}
	return d
}


Measured memory_bytes: 8876