Problem
Welcome to the Enchanted Forest Expedition! As a courageous explorer, your mission is to locate the shortest path to the magical clearing, starting from the enchanted tree. Imagine the forest as a graph: trees are nodes, and paths are edges with unique magical rules that affect your journey. Your goal is to traverse these paths efficiently to reach your destination swiftly. Here's a step-by-step breakdown of what you'll need to do: 1. Visualize the forest as a graph, with nodes (trees) and edges (paths). 2. Understand that each path has a 'weight' or cost based on magical rules, impacting your travel time. 3. Use a suitable pathfinding algorithm to calculate the shortest path from the enchanted tree to the magical clearing. 4. Consider edge cases like loops or multiple paths with the same cost. For example, if two paths have identical costs, ensure your algorithm chooses the optimal one without redundant calculations.
Input format
The first line contains two integers n and m, the number of trees (1 <= n <= 100) and paths (1 <= m <= 500) in the forest. Each of the next m lines describes a path with three integers u, v, and d, where u and v are the trees connected by the path, and d is the distance (1 <= d <= 100). The last line contains two integers s and t, representing the enchanted tree and the magical clearing respectively.
Output format
Output the shortest distance from the enchanted tree to the magical clearing. If there is no path, output -1.
Constraints
1 <= n <= 100, 1 <= m <= 500, 1 <= d <= 100
Sample input
5 6 1 2 10 1 3 20 2 4 15 3 4 30 4 5 10 3 5 50 1 5
Sample output
35