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

public class PriorityQueue<TKey, TValue>
{
    SortedDictionary<TKey, HashSet<TValue>> dict = new SortedDictionary<TKey, HashSet<TValue>>();
    Dictionary<TValue, TKey> rDict = new Dictionary<TValue, TKey>();
    int count = 0;

    public int Count
    {
        get
        {
            return count;
        }
    }

    public void Enqueue(TKey key, TValue value)
    {
        HashSet<TValue> set;
        if (!dict.TryGetValue(key, out set))
        {
            set = new HashSet<TValue>();
            dict[key] = set;
        }

        if (set.Add(value))
        {
            rDict[value] = key;
            count++;
        }
    }

    public KeyValuePair<TKey, TValue> Dequeue()
    {
        var queue = dict.First();
        if (queue.Value.Count <= 1)
        {
            dict.Remove(queue.Key);
        }

        var val = queue.Value.First();
        queue.Value.Remove(val);
        count--;
        rDict.Remove(val);
        return new KeyValuePair<TKey, TValue>(queue.Key, val);
    }

    public KeyValuePair<TKey, TValue> Peek()
    {
        var queue = dict.First();
        var val = queue.Value.First();
        return new KeyValuePair<TKey, TValue>(queue.Key, val);
    }

    public void ChangePriority(TKey newKey, TValue value)
    {
        ChangePriority(rDict[value], newKey, value);
    }

    public void ChangePriority(TKey prevKey, TKey newKey, TValue value)
    {
        var set = dict[prevKey];
        set.Remove(value);
        if (set.Count == 0)
        {
            dict.Remove(prevKey);
        }
        count--;

        Enqueue(newKey, value);
    }

    public bool ContainsValue(TValue val)
    {
        return rDict.ContainsKey(val);
    }
}

public class Rail
{
    public long Silver;
    public long Time;

    public Rail(long silver, long time)
    {
        Silver = silver;
        Time = time;
    }
}

public class Exchange
{
    public long SilverRate;
    public long TimePerOneGold;

    public Exchange(long silverRate, long timePerOneGold)
    {
        SilverRate = silverRate;
        TimePerOneGold = timePerOneGold;
    }
}

public struct Node
{
    public int Point;
    public long Silver;

    public Node(int point, long silver)
    {
        Point = point;
        Silver = silver;
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Node))
        {
            return false;
        }

        var n = (Node)obj;
        return (Point == n.Point && Silver == n.Silver);
    }

    public override int GetHashCode()
    {
        return (Point << 16) ^ (int)Silver;
    }

    public static bool operator ==(Node left, Node right)
    {
        return left.Equals(right);
    }

    public static bool operator !=(Node left, Node right)
    {
        return !(left == right);
    }

    public override string ToString()
    {
        return $"p:{Point} silver:{Silver}";
    }
}

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var N = (int)vals[0];
        var M = (int)vals[1];
        var silver = vals[2];

        var rails = new Rail[N + 1, N + 1];
        var toDict = Enumerable.Range(0, N + 1).Select(_ => new List<int>()).ToArray();
        var exchanges = new Exchange[N + 1];
        long max = 0;
        for (int i = 0; i < M; i++)
        {
            vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            var a = vals[2];
            var b = vals[3];
            var rail = new Rail(a, b);
            max = Math.Max(a, max);
            var u = (int)vals[0];
            var v = (int)vals[1];
            rails[u, v] = rail;
            rails[v, u] = rail;
            toDict[u].Add(v);
            toDict[v].Add(u);
        }
        max *= N - 1;
        silver = Math.Min(max, silver);
        for (int i = 1; i <= N; i++)
        {
            vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            exchanges[i] = new Exchange(vals[0], vals[1]);
        }

        var times = new Dictionary<Node, long>();
        var root = new Node(1, silver);
        var queue = new PriorityQueue<long, Node>();

        void Add(Node n, long t)
        {
            if (!times.ContainsKey(n) || times[n] > t)
            {
                times[n] = t;
                queue.Enqueue(t, n);
            }
        }

        Add(root, 0);
        while (queue.Count > 0)
        {
            var kv = queue.Dequeue();
            var t = kv.Key;
            var node = kv.Value;

            if (node.Silver < max)
            {
                var ex = exchanges[node.Point];
                var next = node;
                next.Silver = Math.Min(node.Silver + ex.SilverRate, max);
                Add(next, t + ex.TimePerOneGold);
            }

            foreach (var nei in toDict[node.Point])
            {
                var rail = rails[node.Point, nei];
                if (node.Silver >= rail.Silver)
                {
                    var next = node;
                    next.Silver -= rail.Silver;
                    next.Point = nei;
                    Add(next, t + rail.Time);
                }
            }
        }

        var bests = Enumerable.Repeat(long.MaxValue, N + 1).ToArray();
        foreach (var kv in times)
        {
            var p = kv.Key.Point;
            var t = kv.Value;
            bests[p] = Math.Min(bests[p], t);
        }

        Console.WriteLine(string.Join(Environment.NewLine, bests.Skip(2)));
    }
}

Measured memory_bytes: 86896