BOJ. Police Car (2618)

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

public class Main {
	static BufferedReader br;
	static int max = 0, maxIdx = 0;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] line;
		int n = toi(br.readLine()), m = toi(br.readLine());
		int[][] cost = new int[n][n];
		for(int[] ar: cost) Arrays.fill(ar, Integer.MAX_VALUE);
		for(int i = 0; i < m; i++) {
			line = getLine();
			int a = toi(line[0]) - 1, b = toi(line[1]) - 1, c = toi(line[2]);
			cost[a][b] = Math.min(cost[a][b], c);
		}

		line = getLine();
		int from = toi(line[0]) - 1, to = toi(line[1]) - 1;
		int[] dijk = new int[n];
		int[] parent = new int[n];
		Arrays.fill(dijk, Integer.MAX_VALUE);
		PriorityQueue<int[]> pq = new PriorityQueue<>((l, r) -> l[1] - r[1]);
		boolean[] visit = new boolean[n];
		pq.add(new int[] { from, 0 });
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			int idx = cur[0], curcost = cur[1];
			if(visit[idx]) continue;
			visit[idx] =  true;
			for(int i = 0; i < n; i++) {
				if(visit[i] || cost[idx][i] == Integer.MAX_VALUE) continue;
				if(curcost + cost[idx][i] < dijk[i]) {
					dijk[i] = curcost + cost[idx][i];
					parent[i] = idx;
					pq.add(new int[] { i, dijk[i] });
				}
			}
		}
		ArrayList<Integer> al = new ArrayList<>();
		int idx = to;
		while(idx != from) {
			al.add(idx);
			idx = parent[idx];
		}
		al.add(from);
		sb.append(dijk[to]).append("\n").append(al.size()).append("\n");
		for(int i = al.size() - 1; i >= 0; i--) sb.append(al.get(i) + 1).append(" ");
		print(sb);
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}