New update is available. Click here to update.

Last Updated: 23 Jul, 2021

Difficulty: Moderate

```
3 3 1 3
1 2 2
1 3 2
2 3 -1
In the above graph, the length of the shortest path between vertex 1 and vertex 3 is 1->2->3 with a cost of 2 - 1 = 1.
```

```
It's guaranteed that the graph doesn't contain self-loops and multiple edges. Also the graph does not contain negative weight cycles.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains four single space-separated integers ‘N’, ‘M’ , ‘src’ and ‘dest’ denoting the number of vertices, the number of edges in the directed graph the source vertex and the destination vertex respectively.
The next ‘M’ lines each contain three single space-separated integers ‘u’, ‘v’, and ‘w’, denoting an edge from vertex ‘u’ to vertex ‘v’, having weight ‘w’.
```

```
For each test case, return an integer denoting the length of the shortest path from ‘src’ to ‘dest’. If no path is possible return 10^9.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 50
1 <= M <= 300
1 <= src, dest <= N
1 <= u,v <= N
-10^5 <= w <= 10^5
Time Limit: 1 sec
```

SIMILAR PROBLEMS

NINJA AND HAPPINESS

Posted: 9 Sep, 2022

Difficulty: Hard

DECODE STRING

Posted: 11 Sep, 2022

Difficulty: Moderate

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Randomly Sorted

Posted: 13 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: