Traffic Light

import java.util.*;

public class Main {

    static class Triple {
        int to, x, y;

        Triple(int to, int x, int y) {
            this.to = to;
            this.x = x;
            this.y = y;
        }
    }

    static final long INFLL = 0x3f3f3f3f3f3f3f3fL;

    static int n, m;
    static long t;
    static List<List<Triple>> gr;

    public static void dijkstra(long t) {
        int s = 0;

        long[] dist = new long[n];
        Arrays.fill(dist, INFLL);
        boolean[] used = new boolean[n];

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        dist[s] = t;
        pq.offer(new long[]{t, s});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long time = current[0];
            int u = (int) current[1];

            if (used[u] || time > dist[u]) continue;
            used[u] = true;

            if (u == n - 1) {
                System.out.println(time);
                return;
            }

            for (Triple edge : gr.get(u)) {
                int to = edge.to;
                int x = edge.x;
                int y = edge.y;
                long sum = x + y;

                long rem = time % sum;

                if (0 <= rem && rem < x) {
                    dist[to] = time;
                    pq.offer(new long[]{time, to});
                } else {
                    dist[to] = time + sum - rem;
                    pq.offer(new long[]{time + sum - rem, to});
                }
            }
        }

        System.out.println(dist[n - 1]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        t = sc.nextLong();

        gr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            gr.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            int x = sc.nextInt();
            int y = sc.nextInt();

            gr.get(a).add(new Triple(b, x, y));
            gr.get(b).add(new Triple(a, x, y));
        }

        dijkstra(t);
    }
}