You cannot submit for this problem because the homework's deadline is due.

Description

Use python3 to implement Dijkstra algorithm.

Submission Format

Submit a tar or zip file including a script named Dijkstra.py and all the related class you have implemented like Fibonacci heap and graph related classes. There are no restriction on the filenames of your imported classes.

IO

Input

The first line contains the number of edges edge_num.
Starting from the second line, information of directed edges will be provided in the form of nodeA nodeB weight.
The final two lines will give you the start and terminate node.

Output

Output the shortest path in the form if a list, starting from the starting node to the terminating node. Note that the node name is expected to be a string.

Sample IO

Sample 1

input

This is the exactly the same case as the one on the lecture slide.

18
s b 4
b s 4
s c 2
c s 2
b d 5
d b 5
c d 8
d c 8
b c 1
c b 1
c e 10
e c 10
d e 2
e d 2
d t 6
t d 6
e t 3
t e 3
s
t

Here s b 4 and b s 4 joinly define an undirected edge with weight 4.

output

['s', 'c', 'b', 'd', 'e', 't']