using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	int enc(int pos, int cost){
		return (pos << 16) + cost;
	}
	public void Solve(){
		int MM = 5000;
		S = Math.Min(MM, S);
		long Inf = (long) 1e18;
		long[][] min = new long[N][];
		bool[][] used = new bool[N][];
		for(int i=0;i<N;i++){
			min[i] = new long[MM + 1];
			used[i] = new bool[MM + 1];
			for(int j=0;j<=MM;j++){
				min[i][j] = Inf;
			}
		}
		List<int>[] E = new List<int>[N];
		for(int i=0;i<N;i++){
			E[i] = new List<int>();
		}
		
		for(int i=0;i<M;i++){
			E[U[i]].Add(i);
			E[V[i]].Add(i);
		}
		
		min[0][S] = 0;
		var SH = new SkewHeap<Pair>();
		SH.Push(new Pair(enc(0, S), 0));
		while(SH.Count > 0){
			var p = SH.Top; SH.Pop();
			int now = p.Pos >> 16;
			int nows = p.Pos % 65536;
			long nowc = p.Cost;
			if(used[now][nows]) continue;
			used[now][nows] = true;
			min[now][nows] = nowc;
			foreach(var e in E[now]){
				int nv = U[e] == now ? V[e] : U[e];
				if(A[e] > nows) continue;
				if(min[nv][nows - A[e]] < nowc + B[e]) continue;
				min[nv][nows - A[e]] = nowc + B[e];
				SH.Push(new Pair(enc(nv, nows - A[e]), nowc + B[e]));
			}
			if(nows < MM){
				int nv = now;
				int ns = nows + C[now];
				if(ns >= MM) ns = MM;
				
				if(min[nv][ns] < nowc + D[now]) continue;
				min[nv][ns] = nowc + D[now];
				if(nv == 1 && ns == 1){
//Console.WriteLine("nowc:{0}, D[now]:{1}",nowc, D[now]);
				}
				SH.Push(new Pair(enc(nv, ns), nowc + D[now]));
			}
		}
//for(int i=0;i<N;i++) Console.WriteLine(String.Join(" ", min[i].Take(10)));
		long[] ans = new long[N-1];
		for(int i=1;i<N;i++){
			ans[i-1] = Inf;
			for(int j=0;j<=MM;j++){
				ans[i-1] = Math.Min(ans[i-1], min[i][j]);
			}
		}
		Console.WriteLine(String.Join("\n", ans));
		
		
	}
	int N, M, S;
	int[] U, V;
	int[] A, B;
	int[] C, D;
	public Sol(){
		var d = ria();
		N = d[0]; M = d[1]; S = d[2];
		U = new int[M];
		V = new int[M];
		A = new int[M];
		B = new int[M];
		for(int i=0;i<M;i++){
			d = ria();
			U[i] = d[0] - 1;
			V[i] = d[1] - 1;
			A[i] = d[2];
			B[i] = d[3];
		}
		C = new int[N];
		D = new int[N];
		for(int i=0;i<N;i++){
			d = ria();
			C[i] = d[0];
			D[i] = d[1];
		}
		
	}
	

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


class Pair : IComparable<Pair> {
	public int Pos;
	public long Cost;
	public Pair(int p, long c) {
		Pos = p; Cost = c;
	}
	public int CompareTo(Pair t) {
		//return this.Cost > t.Cost ? -1 : this.Cost < t.Cost ? 1 : 0;
		return this.Cost > t.Cost ? 1 : this.Cost < t.Cost ? -1 : 0;
	}
}


class SkewHeap<T> where T:IComparable<T>{
	public int Count{
		get{return cnt;}
		private set{cnt=value;}
	}
	
	public SkewHeap(){
		root=null;
		this.Count=0;
	}
	
	public void Push(T v){
		NodeSH<T> p=new NodeSH<T>(v);
		root=NodeSH<T>.Meld(root,p);
		this.Count++;
	}
	
	public void Pop(){
		if(root==null)return;
		root=NodeSH<T>.Meld(root.L,root.R);
		this.Count--;
	}
	
	public T Top{
		get{return root.Val;}
	}
	
	int cnt;
	NodeSH<T> root;
	
	class NodeSH<S> where S : IComparable<S> {
		public NodeSH<S> L, R;
		public S Val;

		public NodeSH(S v){
			Val = v;
			L = null; R = null;
		}
		public static NodeSH<S> Meld(NodeSH<S> a, NodeSH<S> b){
			if(a == null)return b;
			if (b == null) return a;
			if (a.Val.CompareTo(b.Val) > 0) swap(ref a, ref b);
			a.R = Meld(a.R, b);
			swap(ref a.L, ref a.R);
			return a;
		}

		static void swap<U>(ref U x, ref U y) {
			U t = x; x = y; y = t;
		}
	}
}



Measured memory_bytes: 58536