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

namespace contest_Csharp
{
    class Program
    {
        static long power(long a, long b, long modulo)
        {
            long result = 1;
            long buff = a;
            for (long i = 1; i <= b; i *= 2)
            {
                result = result * ((b / i % (2) == 1) ? buff : 1) % modulo;
                buff = (buff * buff) % modulo;
            }
            return result % modulo;
        }
        static void Main(string[] args)
        {
            var vals = Console.ReadLine().Split(' ')
                .Select(x => int.Parse(x)).ToList();
            int N = vals[0];
            int M = vals[1];
            int S = vals[2];
            var pathes = new List<List<(int, long, long)>>(new List<(int, long, long)>[N + 1]);
            for (int i = 0; i < N+1; i++)
            {
                pathes[i] = new List<(int, long, long)>();
            }
            for (int i = 0; i < M; i++)
            {
                var ps = Console.ReadLine().Split(' ')
                    .Select(x => int.Parse(x)).ToList();
                pathes[ps[0]].Add((ps[1], ps[2], ps[3]));
                pathes[ps[1]].Add((ps[0], ps[2], ps[3]));
            }
            var C = new List<long>(new long[N + 1]);
            var D = new List<long>(new long[N + 1]);
            for (int i = 0; i < N; i++)
            {
                var mn = Console.ReadLine().Split(' ')
                    .Select(x => int.Parse(x)).ToList();
                C[i + 1] = mn[0];
                D[i + 1] = mn[1];
            }
            var dp = new List<List<long>>(new List<long>[N + 1]);
            for (int i = 0; i < N+1; i++)
            {
                dp[i] = new List<long>(new long[50 * (N - 1)+1]);
                for (int k = 0; k < 50*(N-1)+1; k++)
                {
                    dp[i][k] = long.MaxValue/2;
                }
            }
            var kousinn = new PriorityQueue<(long, int,long)>();//time,city,money
            int kakutei = 1;
            List<int>[] kakuteilist = new List<int>[N + 1];
            for (int i = 0; i < N+1; i++)
            {
                kakuteilist[i] = new List<int>(new int[50*(N-1)+1]);
            }
            int now = 1;
            
            int money = Math.Min(S, 50 * (N - 1));
            kakuteilist[now][money] = 1;
            dp[now][money] = 0;
            while (kakutei < N*50*(N-1))
            {
                foreach (var item in pathes[now])
                {
                    if (money >= item.Item2)
                    {
                        kousinn.Enqueue((dp[now][money]+item.Item3,
                            item.Item1, money - item.Item2));
                    }
                }
                kousinn.Enqueue((  dp[now][money] + D[now],
                           now, (int)Math.Min(money +C[now], 50 * (N - 1)) ));

                var (getT, getC, getM) = kousinn.Dequeue();
                while (kakuteilist[getC][(int)getM] != 0)
                {
                    (getT, getC, getM) = kousinn.Dequeue();
                }
                
                dp[getC][(int)getM] = getT;
                now = getC;
                money = (int)getM;
                kakuteilist[now][money] = 1;
                kakutei++;
            }
            for (int i = 1; i < N; i++)
            {
                long ans=long.MaxValue/2;
                foreach (var x in dp[i+1])
                {
                    ans = Math.Min(ans, x);
                }
                Console.WriteLine(ans);
            }
        }



    }
    class PriorityQueue<T> where T : IComparable<T>
    {
        private List<T> heap = new List<T>();
        private int lastindex = -1;
        private void swap(int n, int m)
        {
            try
            {
                T wait = heap[n];
                heap[n] = heap[m];
                heap[m] = wait;
            }
            catch
            {
                throw new InvalidOperationException();
            }
        }
        public int Count()
        {
            return lastindex + 1;
        }
        public void Enqueue(T data)
        {
            int p;
            if (lastindex + 1 < heap.Count())
            {
                heap[lastindex + 1] = data;
            }
            else
            {
                heap.Add(data);
            }
            lastindex++;
            p = lastindex;

            while (true)
            {
                if (p > 0 && heap[p].CompareTo(heap[(p - 1) / 2]) <= -1)
                {
                    swap(p, (p - 1) / 2);
                    p = (p - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
        public T Peek()
        {
            return heap[0];
        }
        public T Dequeue()
        {
            T result = Peek();
            heap[0] = default(T);
            swap(0, lastindex);
            lastindex--;
            int p = 0;
            while (true)
            {
                int np;
                if (2 * p + 1 > lastindex)
                {
                    break;
                }
                else
                {
                    np = ((2 * p + 1 == lastindex) || heap[2 * p + 1].CompareTo(heap[2 * p + 2]) <= -1)
                        ? (2 * p + 1) : (2 * p + 2);
                }
                if (heap[p].CompareTo(heap[np]) >= 1)
                {
                    swap(p, np);
                    p = np;
                }
                else
                {
                    break;
                }
            }

            return result;
        }
    }
}


Measured memory_bytes: 43632