Task Scheduler

You are given a set of tasks, each identified by a unique task_id with a specified duration and zero or more dependencies. A dependency means that the given task cannot start until all its dependent tasks have finished.

For each task \( i \), the earliest start time \( S_i \) is defined as: \[ S_i = \max_{j \in D(i)} E_j \] where \( D(i) \) is the set of dependencies for task \( i \) (if there are no dependencies, \( S_i = 0 \)), and the earliest end time \( E_i \) is given by: \[ E_i = S_i + \text{duration}_i \]

Your task is to compute the earliest start and end times for each task and output them in ascending order of task_id.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer N, the number of tasks.

This is followed by N lines, each representing a task in the following format:

task_id duration num_dependencies dependency1 dependency2 ...

For tasks without dependencies, num_dependencies is 0 and no dependency values follow.

outputFormat

Output the computed schedule to standard output (stdout). For each task, output one line containing three space-separated integers: task_id, earliest_start_time, and earliest_end_time. The tasks must be printed in increasing order of task_id.## sample

4
1 3 0
2 2 1 1
3 4 1 2
4 1 1 3

1 0 3
2 3 5
3 5 9
4 9 10