Given a directed weighted graph with negative edges (no negative cycles).
Given a start and end vertex, define the minimum distance between them.
Input:
Given 4 numbers n, m, s, f - number of vertices, number of edges, start and end vertex (starting from 1), respectively.
The next m lines contain 3 numbers each - vertex 1, vertex 2 and the price of transition between vertices.
Output:
It is required to display one number - the answer to the task. If there is no answer, output Inf.
Examples
| # |
Input |
Output |
| 1 |
4 2 1 4
1 2 100500
2 3 100500
|
Inf |