Statement:
You are given a directed weighted graph G and three vertices a,b,c. The goal is to find a path starting in a, passing through b and ending in c, with as small length (sum of weights on edges on the path) as possible.

Graph structure:
Graphs used in test cases have the following structure:

For each test case, parameters N,M,L,U,d1,d2 are selected. For those parameters a graph is created in the following steps:

A grid with N rows and M columns is created.
For each column there will be up to d1 arcs added between nodes in this column.
For each pair of two consecutive columns there will be up to d2 arcs added with ends in nodes from different columns.
Arcs will be added in a random manner - ends of each arc will be selected randomly
Weights of each arc are selected at random, uniformly from interval [L,U]. Edges of the grid are always bidirectional - they are represented as two arcs. Weights of those arcs will have the same weight.
For simplicity, it will always hold a=0, b=M-1, c=(N-1)M. Therefore values a,b,c are not given in input.

Your program needs to finish within 30 seconds. Otherwise it will receive TLE status and no points for given test cases will be awarded. It might be therefore beneficial to implement and use a stopwatch to measure algorithm execution time.

This is a minimization problem - the shorter length of found path, the better. For a given test case, your program will be awarded resb/ resy points, where resb is the result obtained by the best solver for a given test case.

Values of parameters used for graph generation:
(N,M) belongs to { (10,100), (20,200), (30,300), (50,500) }

(L,U) belongs to { (5,15), (5,20), (5,50), (5,200) }

(d1,d2) belongs to { (1,3), (3,1), (5,5), (5,20), (10,50), (0,100) }

Input Format:
In the first line there will be two integers N,M, A denoting number of rows, columns and arcs in the graph.

In each of the following M lines there will be three integers u,v,w, meaning that there is an arc from u to v with weight w in the graph.

It will be guaranteed that for each edge of the grid there will be provided two corresponding arcs, with the same weight.

Additionally, you can assume that node in i-th row and j-th column of the grid will have id equal to i*M+j.

Nodes are indexed from 0 to N x M - .

Output format:
In the first line print an integer K denoting number of nodes on the path.

In the second line print K space-separated integers denoting consecutive nodes on the path.

Example input:
3 4 35
0 1 5
1 0 5
1 2 7
2 1 7
2 3 8
3 2 8
4 5 6
5 4 6
5 6 5
6 5 5
6 7 7
7 6 7
8 9 6
9 8 6
9 10 9
10 9 9
10 11 7
11 10 7
0 4 7
4 0 7
4 8 6
8 4 6
1 5 5
5 1 5
5 9 9
9 5 9
2 6 5
6 2 5
6 10 6
10 6 6
3 7 8
7 3 8
7 11 8
11 7 8
2 9 1

Example output:
11
0 1 5 6 10 11 7 3 2 9 8

This output is would obtain score equal to 5+5+5+6+7+8+8+8+1+6 = 59. It is not an optimal solution.

The path should not contain repeating nodes

import sys
import heapq
import time

def dijkstra(adj, start, end=None):
    N = len(adj)
    dist = [float('inf')] * N
    prev = [None] * N
    dist[start] = 0
    heap = [(0, start)]
    visited = [False] * N

    while heap:
        current_dist, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        if end is not None and u == end:
            break
        for v, w in adj[u]:
            if not visited[v] and dist[v] > current_dist + w:
                dist[v] = current_dist + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev

def reconstruct_path(prev, start, end):
    path = []
    at = end
    while at is not None:
        path.append(at)
        if at == start:
            break
        at = prev[at]
    path.reverse()
    if path[0] == start:
        return path
    else:
        return []

def main():
    import sys
    import threading

    def run():
        start_time = time.time()

        # Read input
        N, M, A = map(int, sys.stdin.readline().split())
        adj = [[] for _ in range(N * M)]
        for _ in range(A):
            u, v, w = map(int, sys.stdin.readline().split())
            adj[u].append((v, w))

        a = 0
        b = M - 1
        c = (N - 1) * M

        # Phase 1: Shortest path from a to b
        dist_a, prev_a = dijkstra(adj, a, end=b)
        path_a_b = reconstruct_path(prev_a, a, b)
        if not path_a_b:
            print("0")
            return

        # Mark nodes used in a to b path
        used_nodes = set(path_a_b)

        # Phase 2: Shortest path from b to c avoiding used_nodes except b
        # Modify the adjacency list to remove used nodes except b
        adj_modified = [[] for _ in range(N * M)]
        for u in range(N * M):
            if u in used_nodes and u != b:
                continue
            for v, w in adj[u]:
                if v in used_nodes and v != b:
                    continue
                adj_modified[u].append((v, w))

        dist_b, prev_b = dijkstra(adj_modified, b, end=c)
        path_b_c = reconstruct_path(prev_b, b, c)
        if not path_b_c:
            print("0")
            return

        # Combine paths, ensuring no duplication of b
        final_path = path_a_b + path_b_c[1:]

        # Output
        print(len(final_path))
        print(' '.join(map(str, final_path)))

    threading.Thread(target=run).start()

if __name__ == "__main__":
    main()

This code doesn't solve the problem unfortunately.