There are N modules in the project. Each module (i) has completion time denoted in number of hours (Hi) and may depend on other modules. If Module x depends on Module y then one needs to complete y before x.

s Project manager, you are asked to deliver the project as early as possible.

Provide an estimation of amount of time required to complete the project.

Input Format:

First line contains T, number of test cases.

For each test case:

First line contains N, number of modules.

Next N lines, each contain:

(i) Module ID

(Hi) Number of hours it takes to complete the module

(D) Set of module ids that i depends on - integers delimited by space.

Output Format:

Output the minimum number of hours required to deliver the project.

Input:

1

5

1 5

2 6 1

3 3 2

4 2 3

5 1 3

output:

16

I know the problem is related to topological sorting.But cant get idea how to find total hours.