PAL3-2-11

package pal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class Main {

    //read
    static public int M; //countOfCities with gas station
    static public int N; //countOfCities without gas station
    static public int H; //highways
    static public int F; //max distance without refueling
    static public int S; //start label
    static public int T; //end label
    //create
//    static public int[][] highways; //matice sousednosti
    static public int[] citiesWeight; //index odpovida label hotelu - weight for dijkstra
    static public boolean[] citiesVisited; // for dijkstra
    static public boolean[] citiesHasGas;
    static public int countOfCities;
    static public int countOfGas;
    static public Queue dijkstraQ; //fronta pro uchovavani navstivenych vrcholu pro Dijkstru
    //reprezentace grafu
    public static HashMap<Integer, Integer> edgeEnd; //vrchol V a delka hrany
    public static HashMap[] vertices; //vrchol U odpovida indexu pole
    public static HashMap<Integer, Integer> edgeEndGas;
    public static HashMap[] gas;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        M = Integer.parseInt(in[0]);
        N = Integer.parseInt(in[1]);
        H = Integer.parseInt(in[2]);
        F = Integer.parseInt(in[3]);
        S = Integer.parseInt(in[4]);
        T = Integer.parseInt(in[5]);
        countOfCities = M + N;
//        highways = new int[countOfCities][countOfCities]; //matice

        edgeEnd = new HashMap<>();
        vertices = new HashMap[countOfCities];
        citiesHasGas = new boolean[countOfCities];
        for (int i = 0; i < M; i++) {
            int inM = Integer.parseInt(br.readLine());
            citiesHasGas[inM] = true; //mesto je pumpa
            countOfGas++;
        }
        edgeEndGas = new HashMap<>();
        gas = new HashMap[countOfGas];
        //mozna udelat for na vertices[x] = new HashMap<>(); a gas = new...
        for (int i = 0; i < H; i++) {
            String[] inH = br.readLine().split(" ");
            int x = Integer.parseInt(inH[0]); //x
            int y = Integer.parseInt(inH[1]); //y
            int l = Integer.parseInt(inH[2]);
            //Integer cannot be converted to HashMap Type
            if (vertices[x] == null) {
                vertices[x] = new HashMap<>();
            }
            vertices[x].put(y, l);
        }
        DijkstraCreateNewGraph(S);
        int lengthEnd = Dijkstra(S);
        System.out.println(lengthEnd);
    }

    public static void DijkstraCreateNewGraph(int from) {
        //       int[] prev = new int[countOfCities]; //nepotřebujem cestu, jen vahy, vzdalenosti
        dijkstraQ = new PriorityQueue();
        citiesWeight = new int[countOfCities]; //index odpovida label vrcholu, weight
        citiesVisited = new boolean[countOfCities];
        int counIndexOfpump = 0;

        int fuel = F;
        for (int i = 0; i < countOfCities; i++) {
            if (i != from) {
                citiesWeight[i] = Integer.MAX_VALUE;
            }


             if (!citiesHasGas[i]) {
                continue;
            } else {
                //zaciname jen z pump
                from = i;
                counIndexOfpump++;
            }
            dijkstraQ.add(from);
            citiesWeight[from] = 0;

            while (!dijkstraQ.isEmpty()) {
                int u = (int) dijkstraQ.poll();
                citiesVisited[u] = true; //visited
                // if(citiesWeight[u] == Integer.MAX) break; //nedostupny vrchol
                //pro kazdyho souseda v vrcholu u
                Set<Integer> keys = vertices[u].keySet();
                for (Integer v : keys) {//jestli soused v nebyl navstiven
                    if (citiesVisited[v] == false) {//spocitej help = citiesWeight[u] + delka mezi uv
                        int length = citiesWeight[u] + (int) vertices[u].get(v);
                        if (length < citiesWeight[v] && length <= fuel) {   //nastav novou dvahu pro v a jeho predka
                            if (!citiesHasGas[v]) {
                                //neni pumpa, nenabije se, ale odecte se
                                fuel -= length;
                            } else {//je pumpa, naplni se
                                fuel = F;
                                //if u a v pumpy, pridej je do noveho redukovaneho grafu
                                if (citiesHasGas[u]) {
                                    if (gas[counIndexOfpump] == null) {
                                        gas[counIndexOfpump] = new HashMap<>();
                                    }
                                    gas[counIndexOfpump].put(v, length);
                                }
                            }
                            dijkstraQ.remove(v);
                            citiesWeight[v] = length;
                            //prev[v] = u;
                            dijkstraQ.add(v);
                        }
                    }
                }
            }
        }
    }

    public static int Dijkstra(int from) {
        //       int[] prev = new int[countOfCities]; //nepotřebujem cestu, jen vahy, vzdalenosti
        dijkstraQ = new PriorityQueue();
        citiesWeight = new int[countOfGas]; //index odpovida label vrcholu, weight
        citiesVisited = new boolean[countOfCities];
        dijkstraQ.add(from);
        citiesWeight[from] = 0;
        for (int i = 0; i < countOfGas; i++) {
            if (i != from) {
                citiesWeight[i] = Integer.MAX_VALUE;
            }
        }
        while (!dijkstraQ.isEmpty()) {
            int u = (int) dijkstraQ.poll();
            citiesVisited[u] = true; //visited
            // if(citiesWeight[u] == Integer.MAX) break; //nedostupny vrchol
            //pro kazdyho souseda v vrcholu u
            Set<Integer> keys = gas[u].keySet();
            for (Integer v : keys) {//jestli soused v nebyl navstiven
                if (citiesVisited[v] == false) {//spocitej help = citiesWeight[u] + delka mezi uv
                    int length = citiesWeight[u] + (int) gas[u].get(v);
                    if (length < citiesWeight[v]) {   //nastav novou dvahu pro v a jeho predka
                        dijkstraQ.remove(v);
                        citiesWeight[v] = length;
                        //prev[v] = u;
                        dijkstraQ.add(v);
                    }
                }
            }
        }
        return citiesWeight[T];
    }
}