B. Artifacts
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
5
1 2 1
1 3 1
1 4 1
5 2 1
2
2 4 2
3 1 2 3
Output
5
-1
Input
10
1 2 5
3 1 3
1 4 8
4 5 1
7 4 2
5 6 4
7 8 1
9 7 10
10 8 5
6
3 9 5 6
2 6 4
1 5
2 5 4
3 8 7 5
3 2 3 4
Output
65
60
53
61
-1
62