← 返回 meta 的题目列表Shortest Path
类型：online_judge
Given a directed graph, find the shortest path from a starting node start to an end node end. The number of nodes is between 1 and 1000. Edge weights are non-negative. You need to return the total weight of the path. You are guaranteed that there is at least one path from start to end.
Input Format:
The first line contains two integers n and m, the number of nodes and edges.
The next m lines each contain three integers u, v, w representing a directed edge from node u to v with weight w.
The last line contains two integers start and end, the starting and ending nodes.
Output Format:
Output the total weight of the shortest path from start to end.
Sample Tests:
Input:
4 4
1 2 1
2 3 2
3 4 1
1 4 4
1 4
Output:
4
Input:
5 5
1 2 1
1 3 5
2 3 1
2 4 2
3 5 1
1 5
Output:
5
Example
Input
4 4
1 2 1
2 3 2
3 4 1
1 4 4
1 4