class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        /*Q26  graph playlist ,bellman ford

            we are not using any temp array here as we dont need result of every iteration
            we just need minimum path from source to every dest and 

            we will return max of all min-paths as our answer
        */

        int path[] = new int[n];
        Arrays.fill(path , Integer.MAX_VALUE);
        path[k-1] = 0;  

        int ans = -1;
        for(int i = 0 ;i < n-1 ; i++){
            
            for(int time[] : times){
                int u = time[0] , v = time[1] , wt = time[2];

                if(path[u-1] == Integer.MAX_VALUE)
                continue;

                //turned into 0 based indexing
                path[v-1] = Math.min(path[v-1] ,path[u-1] + wt );

            }
        }

        //finding maximum of all min paths
        for(int i = 0 ;i < n ; i++)
        ans = Math.max(ans , path[i]);

        //if any min path is still max_Value we return -1
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}