Weighted Paths on NetworkX X15175

networkx

Given a directed graph with n vertices and m weighted arcs, we wish to know the cost of the minimum-cost directed path between two given vertices, if there is one.

Input

Input starts with n and m. Then follow m 3-tuples u,v,w, with u ≠ v, indicating an arc from u to v with weight w. The following will be true: there are no repeated arcs, all weights are positive integers, 0 ≤ u < n and 0 ≤ v < n. Finally, there follows a pair x, y with 0 ≤ x < n and 0 ≤ y < n.

Output

Write the total cost (sum of arc weights) of the path from x to y of least cost, if one exists; otherwise, write “no path”.

Observation

We are authorized to employ the NetworkX library.