#!/usr/bin/env python
import queue

G = [{}]

def setNode(n):
  global G
  G = [{} for i in range(n)]
def addEdge(s,t,w):
  global G
  G[s][t]=w
def solve(s,t):
  global G
  fixed = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x in fixed: continue;
    fixed[x] = w
    if x == t: return w
    for y in G[x]:
      if (y in fixed) == False:
        q.put((w + G[x][y], y))
  return None


n,m = map(int,input().split())
setNode(n)
for i in range(m):
  s,t,w = map(int,input().split())
  addEdge(s,t,w)
  addEdge(t,s,w)
src, dst = map(int,input().split())
print(solve(src,dst))

$ ./dijkstra.py < route03.data 
213

#!/usr/bin/env python
import queue

G = [{}]

def setNode(n):
  global G
  G = [{} for i in range(n)]
def addEdge(s,t,w):
  global G
  G[s][t]=w
def getRoute(via,s,t):
    r = [t]
    y = t
    while y != s:
        y = via[y]
        r.append(y)
    r.reverse()
    return r
def solve(s,t):
  global G
  fixed = {}
  via = {}
  q = queue.PriorityQueue()
  q.put((0,s,None))
  while q.empty() == False:
    w,x,prev = q.get()
    if x in fixed: continue;
    fixed[x] = w
    via[x] = prev
    if x == t:
        return w, getRoute(via,s,t)
    for y in G[x]:
      if (y in fixed) == False:
        q.put((w + G[x][y],y,x))
  return None, None


n,m = map(int,input().split())
setNode(n)
for i in range(m):
  s,t,w = map(int,input().split())
  addEdge(s,t,w)
  addEdge(t,s,w)
src, dst = map(int,input().split())
d,r = solve(src,dst)
print(d)
print(r)

$ ./dijkstraPath.py < route03.data 
213
[0, 4, 5, 10, 15, 20, 24, 25, 29]

import java.util.*;
public class Dijkstra {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 標準入力から読む
        int n = sc.nextInt(); // ノードの数
        int m = sc.nextInt(); // エッジの数
        int[][] mat = new int[n][n]; // ノードの接続関係を表す隣接行列
        for (int i=0; i<n; i++) // 隣接行列を初期化する
            for (int j=0; j<n; j++)
                mat[i][j] = (i==j) ? 0 : -1;
        for (int i=0; i<m; i++) { // エッジの定義を読み込む
            int s = sc.nextInt(); // 始点
            int t = sc.nextInt(); // 終点
            int w = sc.nextInt(); // 重み
            mat[s][t] = mat[t][s] = w;
        }
        int src = sc.nextInt(); // スタートノード
        int dst = sc.nextInt(); // 目的地ノード
        int d = dijkstra(mat,src,dst);
        System.out.println((d==Integer.MAX_VALUE) ? "no route" : d);
    }
    public static int dijkstra(int[][] mat,int src,int dst) {
        int n = mat.length;
        int[] distance = new int[n]; // 各ノードへの最短距離
        boolean[] fixed = new boolean[n]; // 各ノードの最短距離が確定したか?
        for (int i=0; i<n; i++) { // ノードを初期化する
            distance[i] = Integer.MAX_VALUE; // 距離は無限大
            fixed[i] = false;   // 最短距離は未確定
        }
        distance[src] = 0;      // 始点ノードの距離は0
        while (true) {
            int x = minIndex(distance,fixed); // 未確定の中で最小のノード
            if (x == dst) return distance[x]; // 解を発見した
            if (x < 0 || distance[x]==Integer.MAX_VALUE) return Integer.MAX_VALUE; // 非連結グラフ
            fixed[x] = true; // ノード x までの距離は確定となる
            for (int y=0; y<n; y++) { // 各ノードに関して
                if (mat[x][y]>0 && !fixed[y]) { // xからyへエッジが存在し、yが未確定ならば
                    int d2 = distance[x]+mat[x][y];// ｘを経由したyまでの距離
                    // 今までの距離よりも小さければ、それを覚える
                    if (d2 < distance[y]) distance[y] = d2;
                }
            }
        }
    }
    // fixed[]がfalseの中で、distance[]が最小のインデックスを返す
    static int minIndex(int[] distance,boolean[] fixed) {
        int idx = -1;
        for (int i=0; i<fixed.length; i++) {
            if (!fixed[i]) // 未確定で
                if (idx < 0 || distance[idx] > distance[i]) idx = i; // 最小距離のインデックス
        }
        return idx;
    }
}

$ javac Dijkstra.java 
$ java Dijkstra < route03.data 
213

62500 124906
0 1 15
0 250 58
1 2 79
1 251 1
2 3 144
...(略)...

$ javac Dijkstra.java 

$ java Dijkstra < route13.data 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Dijkstra.main(Dijkstra.java:7)

$ java -Xms16g Dijkstra < route13.data  ← ヒープメモリを16Gに拡張して実行する 
22448

*** Dijkstra.java	Mon Jun 19 13:40:15 2023
--- DijkstraPath.java	Mon Jun 19 13:40:28 2023
***************
*** 1,3 ****
  import java.util.*;
! public class Dijkstra {
      public static void main(String[] args) {
--- 1,4 ----
  import java.util.*;
! public class DijkstraPath {
!     static int[] via; // 経由ノード
      public static void main(String[] args) {
***************
*** 19,21 ****
          int d = dijkstra(mat,src,dst);
!         System.out.println((d==Integer.MAX_VALUE) ? "no route" : d);
      }
--- 20,40 ----
          int d = dijkstra(mat,src,dst);
!         if (d == Integer.MAX_VALUE) {
!             System.out.println("no route");
!         } else {
!             System.out.println(d);
!             StringBuilder sb = new StringBuilder();
!             for (int x: getRoute(src, dst)) sb.append(x + " ");
!             System.out.println(sb.toString());
!         }
!     }
!     static ArrayList<Integer> getRoute(int src, int dst) {
!         ArrayList<Integer> r = new ArrayList<>();
!         r.add(dst);
!         int x = dst;
!         while (x != src) {
!             x = via[x];
!             r.add(x);
!         }
!         Collections.reverse(r);
!         return r;
      }
***************
*** 25,26 ****
--- 44,46 ----
          boolean[] fixed = new boolean[n]; // 各ノードの最短距離が確定したか?
+         via = new int[n];  // 経由ノード
          for (int i=0; i<n; i++) { // ノードを初期化する
***************
*** 28,29 ****
--- 48,50 ----
              fixed[i] = false;   // 最短距離は未確定
+             via[i] = -1; // 経由ノードは未確定
          }
***************
*** 39,41 ****
                      // 今までの距離よりも小さければ、それを覚える
!                     if (d2 < distance[y]) distance[y] = d2;
                  }
--- 60,62 ----
                      // 今までの距離よりも小さければ、それを覚える
!                     if (d2 < distance[y]) { distance[y] = d2; via[y] = x; }
                  }

$ javac DijkstraPath.java 
$ java DijkstraPath < route03.data 
213
0 4 5 10 15 20 24 25 29 

$ time (java -Xms16g DijkstraPath < route13.data >/dev/null) 

real	0m19.349s
user	0m30.005s
sys	1m28.251s

import java.util.*;
public class PFSPath {
    static ArrayList<Node> graph = new ArrayList<>();
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in); // 標準入力から読む
	int n = sc.nextInt(); // ノードの数
	int m = sc.nextInt(); // エッジの数
	for (int i=0; i<n; i++)
	    graph.add(new Node(i, Integer.MAX_VALUE)); // 各ノードを生成する
	for (int i=0; i<m; i++) { // エッジの定義を読み込む
	    int s = sc.nextInt(); // 始点
	    int t = sc.nextInt(); // 終点
	    int w = sc.nextInt(); // 重み
	    graph.get(s).addEdge(t,w); // ノードsからtにエッジを張る
	    graph.get(t).addEdge(s,w); // ノードtからsにエッジを張る
	}
	Node src = graph.get(sc.nextInt());	// スタートノード
	Node dst = graph.get(sc.nextInt());	// 目的地ノード
	int d = dijkstra(src, dst);
	if (d ==Integer.MAX_VALUE) {
	    System.out.println("no route");
	} else {
	    System.out.println(d);
	    StringBuilder sb = new StringBuilder();
	    for (Node x: getRoute(src, dst)) sb.append(x.id + " ");
	    System.out.println(sb.toString());
	}
    }
    public static int dijkstra(Node src, Node dst) {
	HashSet<Node> fixed = new HashSet<>(); // 最短距離が確定したノード
	src.d = 0;	// 始点ノードの距離を0とおく
	var queue = new PriorityQueue<Node>();
	queue.add(src);
	while (queue.size() > 0) {
	    Node x = queue.poll(); // キューからの中で最小のノードを取り出す
	    assert !fixed.contains(x);
	    if (x == dst) return x.d; // 解を発見した
	    fixed.add(x); // x を確定ノードとする
	    for (Map.Entry<Integer,Integer> entry: x.edges.entrySet()) { // xから出ている各エッジに対して
		Node y = graph.get(entry.getKey()); // エッジの終端ノード
		int w = entry.getValue(); // エッジの重み
		int d2 = x.d + w; // xを経由したyまでの距離
		if (fixed.contains(y) || d2 >= y.d) continue;　// 「すでに確定済み」or「x経由は遠い」場合何もしない
		if (queue.contains(y)) queue.remove(y); // yがキューに含まれる場合は一旦取り出す
		y.d = d2; // yまでの距離を更新して
		y.via = x; // yの経由地はx
		queue.add(y);  // yをキューに追加する
	    }
	}
	return Integer.MAX_VALUE; // 到達不可能(非連結グラフ)
    }
    static ArrayList<Node> getRoute(Node src, Node dst) { // src->dst の最短経路
	ArrayList<Node> r = new ArrayList<>();
	r.add(dst); // dst から始めて
	Node x = dst;
	while (x != src) { //src まで逆順にたどる
	    x = x.via;
	    r.add(x);
	}
	Collections.reverse(r); // src->dst の順に並べ直す
	return r;
    }
    static class Node implements Comparable<Node> { // ノードの定義 (比較可能)
	int id;    // ノード番号
	int d;     // 距離
	Node via;  // 直前の経由ノード
	HashMap<Integer, Integer> edges; // エッジ: toノード, 重み
	public Node(int id, int d) {
	    this.id = id; 
	    this.d = d;
	    edges = new HashMap<>(); 
	}
	void addEdge(int t, int w) { edges.put(t, w); }
	public int compareTo(Node x) { return d - x.d; }
    }
}

$ java PFSPath < route03.data 
213
0 4 5 10 15 20 24 25 29 

$ time (java PFSPath < route13.data >/dev/null) 

real	0m0.322s
user	0m0.802s
sys	0m0.399s