Relax all edges | V | - 1 times . A simple shortest path from src to any other vertex can have at - most | V | - 1 edges
for ( int i = 0 ; i < V - 1 ; i ++ ) { for ( int j = 0 ; j < E ; j ++ ) { if ( dis [ graph [ j ] [ 0 ] ] != INT_MAX && dis [ graph [ j ] [ 0 ] ] + graph [ j ] [ 2 ] < dis [ graph [ j ] [ 1 ] ] ) dis [ graph [ j ] [ 1 ] ] = dis [ graph [ j ] [ 0 ] ] + graph [ j ] [ 2 ] ; } }