// User function Template for Java
class Pair
{
    int vertex;
    int weight;
    Pair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Solution {
    /**
     * 1. Create a adjancency list, for each node store {vertex, weight} as neighbour.
     * 2. Find the topological sort of given graph and store it in stack
     * 3. Create a distance array, assign all values as Int_MAX except source node will have distance as 0.
     * 4. Run a loop until stack becomes empty
     *    - Relax the edges
     *      - For every neighbour check if distance[neighbour] > distance[currentNode] + weight
     *      - if yes, then update the distance of neighbour
     * 5. if any vertex is unreachable then update distance as -1
     * 6. Return the distance array
     * */
    public int[] shortestPath(int V, int E, int[][] edges) {
        // Step-1 create a adjancency list
        // We will store neighbour nodes as well as weight between the nodes
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Pair>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.get(u).add(new Pair(v, w));
        }
        
        // Step-2 Find the topological sort
        Stack<Integer> st = new Stack<>();
        boolean[] visited = new boolean[V];
        for(int i=0; i<V; i++)
        {
            if(visited[i] == false)
            {
                topoSort(adj, visited, st, i);
            }
        }
        
        // Step-3 define the distance array
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;
        
        // Step-4 relax the edges
        while(!st.isEmpty())
        {
            int node = st.pop();

            for(Pair pair : adj.get(node))
            {
                int vertex = pair.vertex;
                int weight = pair.weight;
                
                // relax the edges
                if(distance[node] != Integer.MAX_VALUE && (distance[vertex] > distance[node] + weight))
                {
                    distance[vertex] = distance[node] + weight;
                }
            }
        }
        
        // Step-5 if vertex is unreachable then update distance as -1
        for(int i=0;i<V;i++)
        {
            if(distance[i] == Integer.MAX_VALUE)
                distance[i] = -1;
        }
        return distance;
    }
    
    
    public void topoSort(ArrayList<ArrayList<Pair>> adj, boolean[] visited, Stack<Integer> st, int node)
    {
        visited[node] = true;
        
        // traversing neighbouring nodes
        for(Pair p : adj.get(node))
        {
            int u = p.vertex;
            if(visited[u] == false)
                topoSort(adj,visited,st,u);
        }
        st.push(node);
    }
}