HackerEarth Dangerous Dungeon problem solution

import java.io.*;
import java.util.*;

public class DangerousCity {
  private static InputReader in;
  private static PrintWriter out;
  
  public static long INF = 1l << 60;
  
  public static void main (String[] args) {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);
    int n = in.nextInt(), m = in.nextInt(), p = in.nextInt();
    
    int[] off = new int[n];
    for (int i = 0; i < n; i++) off[i] = in.nextInt();
    
    ArrayList<Edge>[] fg = new ArrayList[n];
    ArrayList<Edge>[] bg = new ArrayList[n];
    for (int i = 0; i < n; i++) {
      fg[i] = new ArrayList<>();
      bg[i] = new ArrayList<>();
    }
    
    for (int i = 0; i < m; i++) {
      int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
      fg[a].add(new Edge(b, c));
      bg[b].add(new Edge(a, c));
    }
    
    // find shortest distance from every node to end.
    long[] bdist = new long[n];
    Arrays.fill(bdist, 1l << 60);
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    bdist[n-1] = 0;
    pq.add(new Edge(n-1, 0));
    while (pq.size() > 0) {
      Edge e = pq.poll();
      if (bdist[e.to] != e.weight) continue;
      for (Edge next : bg[e.to]) {
        long nn = next.weight + e.weight;
        if (nn < bdist[next.to]) {
          pq.add(new Edge(next.to, bdist[next.to] = nn));
        }
      }
    }
    
    // A* search
    HashMap<Long, Long>[] smods = new HashMap[n];
    for (int i = 0; i < n; i++) smods[i] = new HashMap<>();
    
    long ans = INF;
    if (off[0] != 0) {
      smods[0].put(0l, 0l);
      pq.add(new Edge(0, 0 + bdist[0]));
    }
    while (pq.size() > 0) {
      Edge e = pq.poll();
      long aw = e.weight - bdist[e.to];
      Long x = smods[e.to].get(aw % p);
      if (x == null || x != aw) continue;
      if (e.to == n-1) {
        ans = aw;
        break;
      }
      for (Edge next : fg[e.to]) {
        long nn = next.weight + aw;
        Long y = smods[next.to].get(nn % p);
        if (nn % p != off[next.to] && (y == null || nn < y)) {
          smods[next.to].put(nn % p, nn);
          pq.add(new Edge(next.to, nn + bdist[next.to]));
        }
      }
    }
    
    out.println(ans >= INF ? -1 : ans);
    out.close();
    System.exit(0);
  }
  
  static class Edge implements Comparable<Edge> {
    public int to;
    public long weight;
    public Edge (int to, long weight) {
      this.to = to;
      this.weight = weight;
    }
    public int compareTo(Edge other) {
      return Long.compare(weight, other.weight);
    }
  }
  
  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}