2104 - [Wc2009]shortest

Input

10
9532 7356 9412 5056 3853 4714 1507 4304 3843 3535 
9400 4224 2319 3895 9610 7209 630 4224 5199 1088 
7464 9380 9752 811 3475 6371 5641 6302 5740 9372 
8222 1625 3081 3986 3033 6934 8701 4540 1238 8896 
8075 6991 3121 394 886 9083 3955 7868 9660 5506 
8956 7124 4886 5061 4287 4714 1432 9928 1016 7172 
20
1 6 10 5590
2 5 9 4 3
1 6 8 3526
2 3 4 2 4
1 3 6 1743
2 2 7 2 4
2 1 3 6 5
1 6 9 5831
1 5 6 9487
2 6 7 3 2
2 5 5 3 5
2 1 7 1 2
1 4 5 7904
1 1 6 9571
2 4 5 5 10
1 6 6 159
2 4 5 3 6
1 5 6 4598
2 3 6 5 9
1 1 1 4079