Bellman Ford

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge.
Your task is to find the shortest path from source vertex (vertex number 1) to all other vertices.

Note : use bellman ford algo.
Input Format
First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.
Output Format
Print the shortest distances from the source vertex (vertex number 1) to all other vertices in a line. Print 10^9 in case the vertex can't be reached form the source vertex.
Question Video
Constraints
1<= N <= 10^4
1<= M <= 10^6
1<= ai, bi <= N
-1000 <= wi <= 1000
Sample Input
5 5
1 2 5
1 3 2
3 4 1
1 4 6
3 5 5
Sample Output
5 2 3 7 


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name