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

public class Program
{
    int N, M, S;
    List<Edge>[] edges;
    int[] C;
    long[] D;

    public void Solve()
    {
        var sc = new Scanner();
        N = sc.NextInt();
        M = sc.NextInt();
        S = Math.Min(2500, sc.NextInt());
        edges = new List<Edge>[N];
        for (int i = 0; i < N; i++)
        {
            edges[i] = new List<Edge>();
        }
        for (int i = 0; i < M; i++)
        {
            int u = sc.NextInt() - 1;
            int v = sc.NextInt() - 1;
            int a = sc.NextInt();
            long b = sc.NextLong();
            edges[u].Add(new Edge(v, a, b));
            edges[v].Add(new Edge(u, a, b));
        }

        C = new int[N];
        D = new long[N];
        for (int i = 0; i < N; i++)
        {
            C[i] = sc.NextInt();
            D[i] = sc.NextLong();
        }

        long[] dist = new long[N * 2501].Select(l => long.MaxValue).ToArray();
        var pq = new PriorityQueue<S>((l, r) => dist[Conv(l)].CompareTo(dist[Conv(r)]));
        pq.Enqueue(new S(0, S));
        dist[Conv(0, S)] = 0;

        while (pq.Count > 0)
        {
            var d = pq.Dequeue();
            // 両替
            {
                int nc = Math.Min(2500, d.C + C[d.Pos]);
                long nt = dist[Conv(d)] + D[d.Pos];
                int next = Conv(d.Pos, nc);
                if (nt < dist[next])
                {
                    dist[next] = nt;
                    pq.Enqueue(new S(d.Pos, nc));
                }
            }
            {
                // 移動
                foreach (var e in edges[d.Pos])
                {
                    if (d.C < e.A) continue;
                    int nc = d.C - e.A;
                    long nt = dist[Conv(d)] + e.B;
                    int next = Conv(e.To, nc);
                    if (nt < dist[next])
                    {
                        dist[next] = nt;
                        pq.Enqueue(new S(e.To, nc));
                    }
                }
            }
        }

        var ans = new StringBuilder();
        for (int i = 1; i < N; i++)
        {
            long min = long.MaxValue;
            for (int c = 0; c <= 2500; c++)
            {
                min = Math.Min(min, dist[Conv(i, c)]);
            }
            ans.AppendLine(min.ToString());
        }
        Console.Write(ans);
    }

    public int Conv(S s) => Conv(s.Pos, s.C);
    public int Conv(int p, int c) => p * 2501 + c;

    public static void Main(string[] args) => new Program().Solve();
}

// https://bitbucket.org/camypaper/complib
namespace CompLib.Collections
{
    using System;
    using System.Collections.Generic;

    #region PriorityQueue

    /// <summary>
    /// 指定した型のインスタンスを最も価値が低い順に取り出すことが可能な可変サイズのコレクションを表します．
    /// </summary>
    /// <typeparam name="T">優先度付きキュー内の要素の型を指定します．</typeparam>
    /// <remarks>内部的にはバイナリヒープによって実装されています．</remarks>
    public class PriorityQueue<T>
    {
        readonly List<T> heap = new List<T>();
        readonly Comparison<T> cmp;

        /// <summary>
        /// デフォルトの比較子を使用してインスタンスを初期化します．
        /// </summary>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public PriorityQueue()
        {
            cmp = Comparer<T>.Default.Compare;
        }

        /// <summary>
        /// デリゲートで表されるような比較関数を使用してインスタンスを初期化します．
        /// </summary>
        /// <param name="comparison"></param>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public PriorityQueue(Comparison<T> comparison)
        {
            cmp = comparison;
        }

        /// <summary>
        /// 指定された比較子を使用してインスタンスを初期化します．
        /// </summary>
        /// <param name="comparer"></param>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public PriorityQueue(IComparer<T> comparer)
        {
            cmp = comparer.Compare;
        }

        /// <summary>
        /// 優先度付きキューに要素を追加します．
        /// </summary>
        /// <param name="item">優先度付きキューに追加される要素</param>
        /// <remarks>最悪計算量 O(log N) で実行されます．</remarks>
        public void Enqueue(T item)
        {
            var pos = heap.Count;
            heap.Add(item);
            while (pos > 0)
            {
                var par = (pos - 1) / 2;
                if (cmp(heap[par], item) <= 0)
                    break;
                heap[pos] = heap[par];
                pos = par;
            }

            heap[pos] = item;
        }

        /// <summary>
        /// 優先度付きキューから最も価値が低い要素を削除し，返します．
        /// </summary>
        /// <returns>優先度付きキューから削除された要素．</returns>
        /// <remarks>最悪計算量 O(log N) で実行されます．</remarks>
        public T Dequeue()
        {
            var ret = heap[0];
            var pos = 0;
            var x = heap[heap.Count - 1];

            while (pos * 2 + 1 < heap.Count - 1)
            {
                var lch = pos * 2 + 1;
                var rch = pos * 2 + 2;
                if (rch < heap.Count - 1 && cmp(heap[rch], heap[lch]) < 0) lch = rch;
                if (cmp(heap[lch], x) >= 0)
                    break;
                heap[pos] = heap[lch];
                pos = lch;
            }

            heap[pos] = x;
            heap.RemoveAt(heap.Count - 1);
            return ret;
        }

        /// <summary>
        ///  優先度付きキューに含まれる最も価値が低い要素を削除せずに返します．
        /// </summary>
        /// <returns>優先度付きキューに含まれる最も価値が低い要素．</returns>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public T Peek()
        {
            return heap[0];
        }

        /// <summary>
        /// 優先度付きキュー内の要素の数を取得します．
        /// </summary>
        /// <returns>優先度付キュー内にある要素の数</returns>
        /// <remarks>最悪計算量 O(1) で実行されます．</remarks>
        public int Count
        {
            get { return heap.Count; }
        }

        /// <summary>
        /// 優先度付きキュー内に要素が存在するかどうかを O(1) で判定します．
        /// </summary>
        /// <returns>優先度付キュー内にある要素が存在するならば true，そうでなければ　false．</returns>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public bool Any()
        {
            return heap.Count > 0;
        }

        /// <summary>
        /// 優先度付きキューに含まれる要素を昇順に並べて返します．
        /// </summary>
        /// <remarks>この操作は計算量 O(N log N)で実行されます．</remarks>
        public T[] Items
        {
            get
            {
                var ret = heap.ToArray();
                Array.Sort(ret, cmp);
                return ret;
            }
        }
    }

    #endregion
}

public struct S
{
    public int Pos, C;
    public S(int p, int c)
    {
        Pos = p;
        C = c;
    }
}

struct Edge
{
    public int To, A;
    public long B;
    public Edge(int t, int a, long b)
    {
        To = t;
        A = a;
        B = b;
    }
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 30488