01. Dora the Explorer

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class task1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int edgesCnt = Integer.parseInt(scanner.nextLine());
        int nodes = edgesCnt * 2;


        int[][] graph = new int[nodes][nodes];
        List<int[]> edges = new ArrayList<>();

        for (int i = 0; i < edgesCnt; i++) {
            int[] tokens = Arrays.stream(scanner.nextLine().split(", "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            graph[tokens[0]][tokens[1]] = tokens[2];
            graph[tokens[1]][tokens[0]] = tokens[2];

            edges.add(new int[]{tokens[0], tokens[1]});
            edges.add(new int[]{tokens[1], tokens[0]});
        }



        int extraTime = Integer.parseInt(scanner.nextLine());

        int source = Integer.parseInt(scanner.nextLine());
        int destination = Integer.parseInt(scanner.nextLine());

        int[] distances = new int[graph.length];

        Arrays.fill(distances, Integer.MAX_VALUE);

        int[] prev = new int[graph.length];

        Arrays.fill(prev, -1);


        distances[source] = 0;


        for (int i = 0; i < graph.length; i++) {
            for (int[] edge : edges) {
                int from = edge[0];
                int to = edge[1];
                if (distances[from] != Integer.MAX_VALUE) {
                    int newDistance = distances[from] + graph[from][to] + extraTime;
                    if (newDistance < distances[to]) {
                        distances[to] = newDistance;
                        prev[to] = from;
                    }
                }
            }
        }


        List<Integer> path = new ArrayList<>();

        path.add(destination);

        int node = prev[destination];

        while (node != -1) {
            path.add(node);
            node = prev[node];
        }

        System.out.println("Total time: " + (distances[destination] - extraTime));

        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.println(path.get(i));
        }


    }
}