Flowery Trails

//import java.util.ArrayList;
//import java.util.Arrays;
//
//public class Kilpalaatikko {
//
//    public static void main(String[] args) {
//        IO io = new IO();
//        int n = io.nextInt();
//        long[] table = new long[n];
//        for (int i = 0; i < n; i++) {
//            table[i] = io.nextLong();
//        }
//        Arrays.sort(table);
//        boolean poss = false;
//        for (int i = 2; i < n; i++) {
//            if (table[i] < table[i - 1] + table[i - 2]) {
//                poss = true;
//            }
//        }
//
//        if (poss) {
//            io.print("possible");
//        } else {
//            io.print("impossible");
//        }
//
//        io.close(); // TÄYTYY KUTSUA LOPUKSI, muuten tuloste voi jäädä kirjoittamatta
//
//    }
//
//}
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Queue;

public class Kilpalaatikko {

    public static void main(String[] args) {
        IO io = new IO();
        int n = io.nextInt();
        int m = io.nextInt();
        ArrayList<pari>[] arraylist = new ArrayList[n + 1];
        ArrayList<pari>[] arraylist2 = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            arraylist[i] = new ArrayList<>();
            arraylist2[i] = new ArrayList<>();
        }
        Queue<pari> jono = new PriorityQueue<pari>();

        for (int i = 0; i < m; i++) {
            int a = io.nextInt();
            int b = io.nextInt();
            int c = io.nextInt();

            arraylist[a].add(new pari(b, c, 0));
            arraylist[b].add(new pari(a, c, 0));
        }
        boolean[] visited = new boolean[n + 1];
        int[] d = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            d[i] = Integer.MAX_VALUE;
        }

        int[] monta = new int[n + 1];
        monta[1] = 1;

        d[1] = 0;
        jono.add(new pari(1, 0, 0));

        while (!jono.isEmpty()) {
            pari aa = jono.poll();
            if (aa.y == d[aa.x]) {
                monta[aa.x] += monta[aa.z];
                arraylist2[aa.x].add(new pari(aa.z, aa.y - d[aa.z], 0));

            }
            if (visited[aa.x]) {
                continue;
            }
            visited[aa.x] = true;

            for (pari pp : arraylist[aa.x]) {
                if (!visited[pp.x]) {
                    jono.add(new pari(pp.x, d[aa.x] + pp.y, aa.x));
                    if (d[pp.x] >= pp.y + d[aa.x]) {
                        d[pp.x] = pp.y + d[aa.x];
                    }

                }

            }
//            if(d[n] < Integer.MAX_VALUE){
//                break;
//            }

        }

        long tulos = 0;
        Queue<pari> jono2 = new PriorityQueue();
        jono2.add(new pari(n, 0, 0));
        boolean[] visited2 = new boolean[n + 1];
        while (!jono2.isEmpty()) {

            pari pp = jono2.poll();
            if (pp.x == 1) {
                continue;
            }
        

            for (pari xx : arraylist2[pp.x]) {

                tulos += xx.y;
                if (!visited2[xx.x]) {
                    jono2.add(new pari(xx.x, 0, 0));
                    visited2[xx.x] = true;
                }

            }
          
        }

        io.print(tulos * 2);

        io.close(); // TÄYTYY KUTSUA LOPUKSI, muuten tuloste voi jäädä kirjoittamatta

    }

}

class pari implements Comparable<pari> {

    int x;
    int y;
    int z;

    public pari(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    @Override
    public int compareTo(pari o) {
        return -o.y + this.y;
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED