Shortest Path in a Weighted Graph

Given a directed weighted graph with positive weights, your task is to find the shortest path from a specified source node to a target node using Dijkstra's algorithm.

The graph is represented as an adjacency list: each edge from node \(u\) to node \(v\) has an associated positive weight \(w(u,v)\). The shortest path is the one which minimizes the total sum of the weights along the path.

If there is no valid path from the source to the target, output None.

inputFormat

Input Format:

The input is provided via standard input (stdin). The first line contains two strings denoting the source and target nodes.

The second line contains two integers \(N\) and \(E\) representing the number of nodes and the number of edges respectively.

Each of the following \(E\) lines contains two strings and an integer: \(u\), \(v\), and \(w\), which describe a directed edge from node \(u\) to node \(v\) with weight \(w\).

Note: For simplicity, assume that node names are single uppercase letters.

outputFormat

Output Format:

Output a single line containing the nodes along the shortest path from the source to the target, separated by a single space. If no such path exists, print None.

## sample

A D
4 4
A B 1
A C 4
B C 2
C D 1

A B C D