[APS] Paytolls

// klasicna primena na Dijkstra algoritmot...
import java.util.*;

class Graph<E> {

    int num_nodes;
    GraphNode<E> adjList[];

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes, E[] list) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            adjList[i] = new GraphNode<E>(i, list[i]);
    }

    @SuppressWarnings("unchecked")
    public Graph(int num_nodes) {
        this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
            adjList[i] = new GraphNode<E>(i, null);
    }

    int adjacent(int x, int y) {
        // proveruva dali ima vrska od jazelot so
        // indeks x do jazelot so indeks y
        return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
    }

    void addEdge(int x, int y, float tezina) {
        // dodava vrska od jazelot so indeks x do jazelot so indeks y so tezina
        // i obratno
        if (adjList[x].containsNeighbor(adjList[y])) {
            adjList[x].updateNeighborWeight(adjList[y], tezina);
            adjList[y].updateNeighborWeight(adjList[x], tezina);
        } else{
            adjList[x].addNeighbor(adjList[y], tezina);
            adjList[y].addNeighbor(adjList[x], tezina);
        }
    }

    void deleteEdge(int x, int y) {
        adjList[x].removeNeighbor(adjList[y]);
        adjList[y].removeNeighbor(adjList[x]);
    }

    /*************************** KRUSKAL ***********************************************************************/

    // Metoda koja generira niza od site rebra vo grafot
    public Edge[] getAllEdges() {
        int totalEdges = 0;
        for (int i = 0; i < this.num_nodes; i++) {
            // za sekoe teme go dodavame brojot na sosedi koi gi ima
            totalEdges += this.adjList[i].getNeighbors().size();
        }

        totalEdges /= 2; //bidejki e nenasocen graf, sekoe rebro se javuva kaj dve teminja

        Edge[] edges = new Edge[totalEdges];
        int index = 0;
        for (int i = 0; i < this.num_nodes; i++) {
            for (int j = 0; j < this.adjList[i].getNeighbors().size(); j++) {
                int index1 = this.adjList[i].getIndex();
                // se zemaat indeksot i tezinata na j-ot sosed na temeto i
                int index2 = this.adjList[i].getNeighbors().get(j).node
                        .getIndex();
                float weight = this.adjList[i].getNeighbors().get(j).weight;
                if(index2>index1) //bidejki grafot e nenasocen, da ne go zemame sekoe rebro dva pati
                    edges[index++] = new Edge(index1, index2, weight);
            }
        }

        return edges;
    }

    // Metoda koja gi sortira site rebra
    private void sortEdges(Edge[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = i + 1; j < edges.length; j++) {
                if (edges[i].getWeight() > edges[j].getWeight()) {
                    Edge tmp = edges[i];
                    edges[i] = edges[j];
                    edges[j] = tmp;
                }
            }
        }

    }

    //Metoda koja pravi unija na dve drva
    private void union(int u, int v, int[] vrski){
        int findWhat, replaceWith;

        if(u < v){
            findWhat = vrski[v];
            replaceWith = vrski[u];
        }
        else{
            findWhat = vrski[u];
            replaceWith = vrski[v];
        }

        //za dvete poddrva stava ist index
        //vo vrski t.e. gi spojuva
        for(int i=0; i<vrski.length; i++){
            if(vrski[i] == findWhat){
                vrski[i] = replaceWith;
            }
        }
    }

    List<Edge> kruskal() {
        /*
         * Pomoshna niza za sledenje na kreiranite drva
         * Ako dve teminja se del od isto poddrvo
         * togash imaat ista vrednost vo nizata
         */
        int vrski[] = new int[this.num_nodes];

        // niza koja gi sodrzi site rebra
        Edge[] edges = this.getAllEdges();
        // se sortiraat rebrata spored tezinite vo neopagjacki redosled
        this.sortEdges(edges);

        // inicijalizacija na pomosnata niza za evidencija,
        // sekoj jazel si e posebno drvo
        for (int i = 0; i < this.num_nodes; i++)
            vrski[i] = i;

        // lista koja kje gi sodrzi MST rebra
        List<Edge> mstEdges = new ArrayList<Edge>();

        for(int i=0; i<edges.length; i++){
            //za sekoe rebro vo sortiran redosled
            Edge e = edges[i];

            if(vrski[e.getFrom()] != vrski[e.getTo()]){
                //ako teminjata na ova rebro ne se vo isto poddrvo
                //ova rebro e MST rebro
                mstEdges.add(e);
                //sega dvete teminja treba da se vo isto poddrvo
                //t.e se pravi merge (unija) t.s. vo nizata vrski
                //za site elementi od dvete poddrva
                //go setira istiot (najmal) element od dvete poddrva
                //vrski = this.union(e.getFrom(), e.getTo(), vrski);
                this.union(e.getFrom(), e.getTo(), vrski);
            }

            //ako sme dodale num_nodes-1 rebra moze da prestaneme
            if(mstEdges.size()==(this.num_nodes-1))
                break;
        }

        return mstEdges;
    }

    /*******************************************************************************************************/
    /************************ PRIM **************************************************************************/

    //Metoda koja go naogja najmaloto rebro do
    //teme na neposeten sosed
    private Edge getMinimalEdge(boolean[] included){
        int index1 = Integer.MAX_VALUE, index2 = Integer.MAX_VALUE;
        float minweight = Float.MAX_VALUE;

        for(int i=0;i<this.num_nodes;i++){
            if(included[i]){
                //ako e vkluceno temeto i
                //izmini gi negovite nevkluceni sosedi
                Iterator<GraphNode<E>.GraphNodeNeighbor<E>> it = adjList[i].getNeighbors().iterator();
                while(it.hasNext()){
                    GraphNode<E>.GraphNodeNeighbor<E> pom = it.next();
                    //ako sosedot ne e poseten i ima do sega najmala tezina
                    if(!included[pom.node.getIndex()] && pom.weight<minweight){
                        index1 = i;
                        index2 = pom.node.getIndex();
                        minweight = pom.weight;
                    }
                }
            }
        }

        if(minweight<Float.MAX_VALUE){
            Edge ret = new Edge(index1, index2, minweight);
            return ret;
        }
        return null;
    }


    List<Edge> prim(int start_index) {
        // lista koja kje gi sodrzi MST rebra
        List<Edge> mstEdges = new ArrayList<Edge>();

        boolean included[] = new boolean[this.num_nodes];
        for(int i=0;i<this.num_nodes;i++)
            included[i]=false;

        included[start_index] = true;

        for(int i=0;i<this.num_nodes-1;i++){
            Edge e = this.getMinimalEdge(included);
            if(e==null){
                System.out.println("Ne mozat da se povrzat site jazli");
                break;
            }
            included[e.getFrom()] = included[e.getTo()] = true;
            mstEdges.add(e);
        }

        return mstEdges;
    }

    /*******************************************************************************************************/
    /***************** DIJKSTRA ******************************************************************************/

    float[] dijkstra(int from) {

        /* Minimalna cena do sekoe od teminjata */
        float distance[] = new float[this.num_nodes];
        /* dali za temeto e najdena konecnata (minimalna) cena */
        boolean finalno[] = new boolean[this.num_nodes];
        for (int i = 0; i < this.num_nodes; i++) {
            distance[i] = -1;
            finalno[i] = false;
        }

        finalno[from] = true;
        distance[from] = 0;

        /*
         * vo sekoj cekor za edno teme se dobiva konecna minimalna cena
         */
        for (int i = 1; i < this.num_nodes; i++) {
            /* za site sledbenici na from presmetaj ja cenata */
            Iterator<GraphNode<E>.GraphNodeNeighbor<E>> it = adjList[from].getNeighbors().iterator();
            while (it.hasNext()) {
                GraphNode<E>.GraphNodeNeighbor<E> pom = it.next();
                /* ako grankata kon sosedot nema konecna cena */
                if (!finalno[pom.node.getIndex()]) {
                    /* ako ne e presmetana cena za temeto */
                    if (distance[pom.node.getIndex()] <= 0) {
                        distance[pom.node.getIndex()] = distance[from]
                                + pom.weight;
                    }
                    /* inaku, ako e pronajdena poniska */
                    else if (distance[from] + pom.weight < distance[pom.node
                            .getIndex()]) {
                        distance[pom.node.getIndex()] = distance[from]
                                + pom.weight;
                    }
                }
            }

            /* najdi teme so min. cena koja ne e konecna */
            boolean minit = false; /* min. ne e inicijaliziran */
            int k = -1;
            float minc = -1;
            /* proveri gi site teminja */
            for (int j = 0; j < this.num_nodes; j++) {
                if (!finalno[j] && distance[j] != -1) { /*ako cenata ne e  konecna*/
                    if (!minit) { /* ako ne e inicijaliziran minimumot */
                        minc = distance[k = j]; /* proglasi go ova e minimum */
                        minit = true; /* oznaci deka min e inicijaliziran */
                    }
                    /* proveri dali e pronajdeno teme so pomala cena */
                    else if (minc > distance[j] && distance[j] > 0)
                        minc = distance[k = j];
                }
            }
            finalno[from = k] = true;
        }

        return distance;

    }

    /*******************************************************************************************************/

    @Override
    public String toString() {
        String ret = new String();
        for (int i = 0; i < this.num_nodes; i++)
            ret += adjList[i] + "\n";
        return ret;
    }
    public GraphNode<E> getNode(String ime){
        for(int i=0;i<this.adjList.length;i++){
            if(adjList[i].getInfo().equals(ime)) return adjList[i];
        }
        return null;
    }

}
class GraphNodeNeighbor<E> {
    GraphNode<E> node;
    float weight;

    public GraphNodeNeighbor(GraphNode<E> node, float weight) {
        this.node = node;
        this.weight = weight;
    }

    public GraphNodeNeighbor(GraphNode<E> node) {
        this.node = node;
        this.weight = 0;
    }

    @Override
    public boolean equals(Object obj) {
        @SuppressWarnings("unchecked")
        GraphNodeNeighbor<E> pom = (GraphNodeNeighbor<E>)obj;
        return pom.node.equals(this.node);
    }
}
class GraphNode<E> {
    private int index; //index (reden broj) na temeto vo grafot
    private E info;
    private LinkedList<GraphNodeNeighbor<E>> neighbors;

    public GraphNode(int index, E info) {
        this.index = index;
        this.info = info;
        neighbors = new LinkedList<GraphNodeNeighbor<E>>();
    }

    public boolean containsNeighbor(GraphNode<E> o){
        GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
        return neighbors.contains(pom);
    }

    public void addNeighbor(GraphNode<E> o, float weight){
        GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,weight);
        neighbors.add(pom);
    }

    public void removeNeighbor(GraphNode<E> o){
        GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
        if(neighbors.contains(pom))
            neighbors.remove(pom);
    }

    @Override
    public String toString() {
        String ret= "INFO:"+info+" SOSEDI:";
        for(int i=0;i<neighbors.size();i++)
            ret+="("+neighbors.get(i).node.info+","+neighbors.get(i).weight+") ";
        return ret;

    }

    public void updateNeighborWeight(GraphNode<E> o, float weight){
        Iterator<GraphNodeNeighbor<E>> i = neighbors.iterator();
        while(i.hasNext()){
            GraphNodeNeighbor<E> pom = i.next();
            if(pom.node.equals(o))
                pom.weight = weight;
        }

    }

    @Override
    public boolean equals(Object obj) {
        @SuppressWarnings("unchecked")
        GraphNode<E> pom = (GraphNode<E>)obj;
        return (pom.info.equals(this.info));
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public E getInfo() {
        return info;
    }

    public void setInfo(E info) {
        this.info = info;
    }

    public LinkedList<GraphNodeNeighbor<E>> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(LinkedList<GraphNodeNeighbor<E>> neighbors) {
        this.neighbors = neighbors;
    }
    class GraphNodeNeighbor<E> {
        GraphNode<E> node;
        float weight;

        public GraphNodeNeighbor(GraphNode<E> node, float weight) {
            this.node = node;
            this.weight = weight;
        }

        public GraphNodeNeighbor(GraphNode<E> node) {
            this.node = node;
            this.weight = 0;
        }

        @Override
        public boolean equals(Object obj) {
            @SuppressWarnings("unchecked")
            GraphNodeNeighbor<E> pom = (GraphNodeNeighbor<E>)obj;
            return pom.node.equals(this.node);
        }

    }
}
class Edge{
    private int fromVertex, toVertex;
    private float weight;
    public Edge(int from, int to, float weight){
        this.fromVertex = from;
        this.toVertex = to;
        this.weight = weight;
    }

    public int getFrom(){
        return this.fromVertex;
    }
    public int getTo(){
        return this.toVertex;
    }
    public float getWeight(){
        return this.weight;
    }

    @Override
    public String toString() {
        return "("+fromVertex+","+toVertex+")="+weight+" ";
    }
}
public class Paytolls {
    public static void main(String[] args) {
        Scanner input= new Scanner(System.in);
        int numCities= Integer.parseInt(input.nextLine());
        Graph<String> graph= new Graph<>(numCities);
        for(int i=0;i<numCities;i++){
            graph.adjList[i].setIndex(i);
            graph.adjList[i].setInfo(i+"");
        }
        String[] info= input.nextLine().split("\\s+");
        int start= Integer.parseInt(info[0])-1;
        int end= Integer.parseInt(info[1])-1;
        int numPaths= Integer.parseInt(input.nextLine());
        for(int i=0;i<numPaths;i++){
            String[] info_path= input.nextLine().split("\\s+");
            graph.addEdge(Integer.parseInt(info_path[0])-1,Integer.parseInt(info_path[1])-1,Float.parseFloat(info_path[2]));
        }
        float[] distances= graph.dijkstra(start);
        System.out.println((int) distances[end]);
    }
}
/*
4
1 3
5
1 2 4
1 3 15
2 3 3
3 4 15
1 4 13
------
7

50
9 42
54
1 2 38
2 3 170
4 1 142
5 3 520
2 6 191
4 7 106
6 8 540
6 9 965
6 10 309
9 11 43
9 12 506
11 13 937
14 13 877
15 11 506
16 12 516
13 17 156
14 18 981
16 19 420
20 16 857
18 21 45
19 22 592
19 23 972
24 22 938
25 22 150
26 24 920
25 27 39
26 28 670
27 29 484
30 28 464
27 31 232
32 30 870
29 33 114
32 34 366
32 35 179
32 36 748
33 37 630
38 36 355
35 39 680
36 40 130
41 38 955
42 41 697
43 39 815
41 44 573
43 45 820
46 45 266
47 45 422
48 47 218
49 45 924
46 50 63
45 41 966
20 31 267
11 12 900
36 26 985
36 34 578
---------
3074
 */