public static void shortestPaths(List<Edge>[] edges, int s, long[] prio, int[] pred) {
    Arrays.fill(pred, -1);
    Arrays.fill(prio, Long.MAX_VALUE);
    prio[s] = 0;
    Queue<QItem> q = new PriorityQueue<QItem>();
    q.add(new QItem(0, s));
    while (!q.isEmpty()) {
      QItem cur = q.poll();
      if (cur.prio != prio[cur.u])
        continue;
      for (Edge e : edges[cur.u]) {
        int v = e.t;
        long nprio = prio[cur.u] + e.cost;
        if (prio[v] > nprio) {
          prio[v] = nprio;
          pred[v] = cur.u;
          q.add(new QItem(nprio, v));
        }
      }
    }
  }