INPUT 
9
10
1 4 5
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16
29
 1  6 11
 2 11  9
 3  8  7
 4 12  8
 5  9 20
 6  3  2
 7  1  6
 8  2 13
 9 15  1
10 14 17
11 13 19
12  5 18
13  7  3
14 10 16
15 28 31
16 33 29
17 30 27
18 34 28
19 31 40
20 25 22
21 23 42
22 24 33
23 37 21
24 36 37
25 35 39
26 27 38
27 29 23
28 32 36
29 41 41

4
1 2	4
2 3	3
3 1	2
4 4	1
5
1 3	5
2 4	3
3 2	2
4 1	1
5 6	6
7
1 5	3
2 4	1
3 20	15
4 3	4
5 10	35
6 15	6
7 2	2
20
1 12 2
2 17 4
3 16 5
4 15 24
5 22 23
6 6 21
7 19 14
8 14 9
9 11 13
10 5 12
11 24 7
12 20 10
13 26 19
14 13 20
15 18 8
16 23 16
17 7 15
18 21 18
19 8 11
20 10 17
8
1 4 2
2 12 8
3 20 1
4 9 4
5 14 13
6 19 5
7 7 7 
8 15 9
11
1 21 14
2  9 11
3 12 12
4 10 10
5 20 6
6 18 3
7 15 1
8 14 2
9 17 4
10 23 9
11 22 5

OUTPUT
10 8 7 3 4 9 5 6 2 1 10 
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2 
29 9 23 29 21 12 8 7 6 13 27 18 24 25 19 26 5 1 3 4 16 28 22 14 2 20 17 15 11 10 
4 4 2 1 3 
5 4 2 5 1 3 
7 2 6 3 5 7 1 4 
20 1 2 11 13 5 4 6 10 3 12 16 18 14 17 19 8 15 7 20 9 
8 3 6 5 7 1 4 8 2 
11 7 11 10 1 3 2 8 6 5 4 9 

另外行末有空格差评