题解 | #最短路径问题#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if (n == 0 && m == 0) break;
            List<List<Edge>> graph = new ArrayList<>();
            for (int i = 0; i <= n; i++) graph.add(new LinkedList<>());
            for (int i = 0; i < m; i++) {
                int from = sc.nextInt();
                int to = sc.nextInt();
                int dist = sc.nextInt();
                int cost = sc.nextInt();
                graph.get(from).add(new Edge(to, dist, cost));
                graph.get(to).add(new Edge(from, dist, cost));
            }
            int s = sc.nextInt();
            int t = sc.nextInt();
            int[] minDist = new int[n + 1];
            int[] minCost = new int[n + 1];
            boolean[] visited = new boolean[n + 1];
            Arrays.fill(minDist, Integer.MAX_VALUE);
            Arrays.fill(minCost, Integer.MAX_VALUE);
            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
            minDist[s] = 0;
            minCost[s] = 0;
            pq.offer(new int[]{s, 0});
            while (!pq.isEmpty()) {
                int[] cur = pq.poll();
                int from = cur[0];
                if (visited[from]) continue;
                visited[from] = true;
                for (Edge edge : graph.get(from)) {
                    int to = edge.to;
                    int dist = edge.dist;
                    if (!visited[to] && (minDist[from] + dist < minDist[to] || minDist[from] + dist == minDist[to] && minCost[from] + edge.cost < minCost[to])) {
                        minDist[to] = minDist[from] + dist;
                        minCost[to] = minCost[from] + edge.cost;
                        pq.offer(new int[]{to, minDist[to]});
                    }
                }
            }
            System.out.println(minDist[t] + " " + minCost[t]);
        }
    }
    private static class Edge {
        private final int to, dist, cost;
        private Edge(int to, int dist, int cost) {
            this.to = to;
            this.dist = dist;
            this.cost = cost;
        }
    }
}