import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;



class Oblig2V2 {


    private static String   filename = "";
    private static Scanner  sc;
    private static Graph    graph;
    private static int      cnt = 0;


    public static void main (String [] args) throws IOException  {
        if (args != null) {
            if (args[0] != null)
                filename = args[0];
            if (!filename.equals("")) {
                try {
                    // Create a scanner-instance based on the file specified:
                    sc = new Scanner(new File(filename));

                    // Get the number of vertices:
                    cnt = Integer.parseInt(sc.next());

                    // Line feed:
                    sc.nextLine();
                    sc.nextLine();

                    // Holds on to the vertices indegrees, where the KEY = VERTEX ID, and the VALUE = VERTEX IDS OF OUTDEGREES.
                    HashMap<Integer, ArrayList<Integer>> edgesOverview = new HashMap<Integer, ArrayList<Integer>>();

                    if (cnt > 0) {
                        // Create a new graph:
                        graph = new Graph(cnt);


                        while (sc.hasNextLine()) {
                            // Get vertex attributes:
                            String [] line = sc.nextLine().split("[\t ]+");

                            // If-statement to make sure the file corresponds to the input requirements.
                            if (line.length < 4) {
                                break;
                            }

                            graph.addVertex(Integer.parseInt(line[0]), line[1], Integer.parseInt(line[2]), Integer.parseInt(line[3]));

                            // Add the edge(s) to the graph:
                            int newEdge = Integer.parseInt(line[4]);

                            // For all edges:
                            for (int i=4; newEdge > 0 && i < line.length; i++) {
                                // If startnode already exists in edgesOverview
                                if (edgesOverview.get(newEdge) != null) {
                                    // Pull out nodeList, add the node, and put back into hashmap
                                    ArrayList<Integer> nodeList = edgesOverview.get(newEdge);
                                    nodeList.add(Integer.parseInt(line[0]));
                                    edgesOverview.put(newEdge, nodeList);
                                } else {
                                    // Create a new nodeList, add the node, and put into hashmap
                                    ArrayList<Integer> nodeList = new ArrayList<Integer>();
                                    nodeList.add(Integer.parseInt(line[0]));
                                    edgesOverview.put(newEdge, nodeList);
                                }
                                // Get the next edge-ID:
                                newEdge = Integer.parseInt(line[i+1]);
                            }
                        }

                        // Assign edges to all nodes:
                        graph.setEdges(edgesOverview);
                    }

                    // Check to see if the graph is acyclic.
                    graph.topSort(edgesOverview);

                } catch (FileNotFoundException e) {
                    System.out.println("File was not found.");
                }
            } else {
                System.out.println("Vertex counter has to be a positive integer.");
            }
        }
    }
}

class Graph {

    // Contains the graph data structure.
    protected HashMap<Integer, Vertex> graph;

    // Contains the number of vertices in the graph.
    protected int numVertex;

    // Binary Heap storing vertices after topological sorting.
    BinaryHeap heap;

    /**
    * Default constructor
    * @param numVertex      the number of vertices specified by the input file
    */
    public Graph (int numVertex) {
        graph = new HashMap<Integer, Vertex>();
        this.numVertex = numVertex;
        heap = new BinaryHeap(numVertex);
    }

    /**
    * Adds a new Vertex instace to the graph.
    * @param id id of vertex
    * @param name   name of vertex
    * @param est    estimated time of this vertex
    * @param mp manpower required for this vertex
    */
    public void addVertex(int id, String name, int est, int mp) {
        graph.put(id, new Vertex(id, name, est, mp));
    }

    /**
    * Adds all edges in the graph based on input file
    * @param edges      holds overview of all edges, where key identifies out-node, and value identifies a collection of in-nodes.
    */
    public void setEdges(HashMap<Integer, ArrayList<Integer>> edges) {
        for ( Integer vtx_key : edges.keySet() ) {
            for ( Integer edgesTo : edges.get(vtx_key) ) {
                graph.get(vtx_key).addEdge(graph.get(edgesTo));
            }
        }
    }


    /**
     * Topological search linear-time complexity function to ensure graph is acyclic from the beginning.
     * @see findVertexWithIndegreeZero()
     */
    public void topSort(HashMap<Integer, ArrayList<Integer>> edgesOverview) {
        Stack<Vertex> queue = new Stack<Vertex>();
        int counter = 0;
        findVertexWithIndegreeZero(queue);
        System.out.println("Topological sort successfull! Graph was acyclic.");

        while (!queue.isEmpty()) {
            Vertex v = queue.pop();
            v.topNum = ++counter;
            v.findEarliestStart();
            heap.insert(v);

            for (Vertex w : v.getEdges()) {
                w.decrementIndegree();
                if (w.getIndegree() <= 0) {
                    w.increaseCost(v.getCost());
                    queue.add(w);
                }
            }
        }
        // Resets the vertices back to original indegree build-up
        setEdges(edgesOverview);

        // Prints the process
        heap.printprocess();
    }

    /**
     * Finds all vertices with 0 indegree (no dependancies). Will end program if a cycle is found between 2 vertices.
     * @param   queue   the queue to insert 0-indegree vertices
     * @see     Vertex.isCyclic()
     */
    public void findVertexWithIndegreeZero(Stack<Vertex> queue) {
        for ( Integer vKey : graph.keySet() ) {
            // Will end program if the vertex is found to be cyclic.
            graph.get(vKey).isCyclic();
            if (graph.get(vKey).getIndegree() <= 0)
                queue.push(graph.get(vKey));
        }
    }


    private class BinaryHeap {

        private int size;
        private Vertex array [];
        private int numElements;

        public BinaryHeap (int size) {
            this.size = size;
            array = new Vertex[size];
            numElements = 0;
        }

        public void insert(Vertex v) {
            if (numElements == array.length-1)
                enlargeArray( array.length * 2 + 1 );

            int hole = ++numElements;
            for ( ; hole > 1 && v.compareTo(array[hole/2]) < 0; hole /= 2)
                array[hole] = array[hole/2];

            array[hole] = v;
        }

        public Vertex deleteMin() {
            if (numElements == 0)
                return null;

            Vertex minItem = findMin();
            array[1] = array[numElements--];
            percolateDown(1);

            return minItem;
        }

        public Vertex findMin() {
            return array[1];
        }

        private void percolateDown(int hole) {
            int child;
            Vertex tmp = array[hole];

            for ( ; hole * 2 <= numElements; hole = child) {
                child = hole * 2;
                if (child != numElements && array[child+1].compareTo(array[child]) < 0)
                    child++;
                if (array[child].compareTo(tmp) < 0)
                    array[hole] = array[child];
                else
                    break;
            }
            array[hole] = tmp;
        }

        public void enlargeArray(int newsize) {
            Vertex [] tmp_array = new Vertex[newsize];

            for (int i=0; i<array.length; i++) {
                tmp_array[i] = array[i];
            }

            array = tmp_array;
        }

        public void printprocess() {
            int totalCost = 0;
            int timeCounter = 0;

            // Stores all vertices that already has been started.
            ArrayList<Vertex> hasBeenStarted = new ArrayList<Vertex>();

            // Stores all vertices that are to be started at a later time.
            Stack<Vertex> toBeStarted = new Stack<Vertex>();

            // Finds all vertices with indegree zero from priority heap.
            Vertex vtx = deleteMin();
            toBeStarted.add(vtx);
            while (findMin().getIndegree() == 0) {
                toBeStarted.add(deleteMin());
            }

            // Outputs the process.
            while (!toBeStarted.isEmpty() || !hasBeenStarted.isEmpty()) {
                System.out.println("TIME: " + timeCounter);

                // Prompts the next tasks at this TIME.
                while (toBeStarted.size() != 0 && timeCounter == toBeStarted.peek().earliestStart) {
                    vtx = toBeStarted.pop();
                    hasBeenStarted.add(vtx);
                    System.out.println("\t\tStarting: " + vtx.getId() + ".");
                }


                for (Vertex v : hasBeenStarted) {
                    if (timeCounter == v.cost) {
                        System.out.println("\t\tFinished: " + v.getId() + ".");
                        hasBeenStarted.remove(v);
                    }
                }


                vtx = deleteMin();
                int newNodeStart = vtx.cost - vtx.estimate;
                toBeStarted.push(vtx);

                // Finds out whether any of the already started tasks is finished, if so, output info and remove from the list.
                for (Vertex v : hasBeenStarted) {
                    if ((timeCounter + v.estimate) < newNodeStart)
                        timeCounter = timeCounter + v.estimate;
                    else
                        timeCounter = newNodeStart;
                }
            }
            System.out.println("Total cost was: " + totalCost);
        }
    }

    private class Vertex {

        public int                      topNum;
        public int                      dist;

        private int                     id, estimate, manpower;
        private String                  name;
        int                             earliestStart, latestStart, indegree, outdegree;
        ArrayList<Vertex>               pointsTo, isPointedAt;
        private int                     cost;


        public Vertex(int id, String name, int estimate, int manpower) {
            this.id = id;
            this.name = name;
            this.estimate = estimate;
            this.manpower = manpower;
            cost = estimate;
            pointsTo = new ArrayList<Vertex>();
            isPointedAt = new ArrayList<Vertex>();
        }


        public int getId() {
            return id;
        }

        public int getIndegree() {
            return indegree;
        }

        public int getEst() {
            return estimate;
        }

        public void incrementIndegree() {
            indegree += 1;
        }

        public void decrementIndegree() {
            indegree--;
        }

        public int getOutdegree() {
            return outdegree;
        }

        public void incrementOutdegree() {
            outdegree++;
        }

        public void decrementOutdegree() {
            outdegree--;
        }

        public void increaseCost(int num) {
            cost += num;
        }

        public int getCost() {
            return cost;
        }

        public void addEdge(Vertex w) {
            pointsTo.add(w);
            incrementOutdegree();
            w.incrementIndegree();
            w.isPointedAt.add(this);
        }

        public void findEarliestStart() {
            for ( Vertex v : pointsTo ) {
                v.earliestStart = cost;
            }
        }

        public void findLatestStart() {
            int maxEarliestStart = 0;
            for ( Vertex v : pointsTo ) {
                if (v.earliestStart > maxEarliestStart)
                    maxEarliestStart = v.earliestStart;
            }
            latestStart = (maxEarliestStart - estimate) <= earliestStart ? earliestStart : (maxEarliestStart - estimate);

            for ( Vertex v : pointsTo ) {
                v.findLatestStart();
            }
        }

        public int getSlack() {
            return latestStart - earliestStart;
        }

        public ArrayList<Vertex> getEdges() {
            return pointsTo;
        }

        public boolean pointsAt(Vertex w) {
            return pointsTo.contains(w);
        }

        /**
         * Checks to see if the vertex is part of a cyclic path; if this is the case, the program will be terminated.
         */
        public void isCyclic() {
            for ( Vertex w : pointsTo) {
                if (this.pointsAt(w) && w.pointsAt(this)) {
                    System.out.println("ERROR: Graph is cyclic! Occurs between " + w.getId() + " and " + getId() + ".");
                    System.exit(0);
                }
            }
        }

        public int compareTo(Vertex v) {
            if (v.getCost() > cost)
                return -1;
            else if (v.getCost() < cost)
                return 1;
            return 0;
        }
    }
}