4 5
1 2 1
1 3 2
2 4 2
3 4 1
2 3 1
2 1
1 2 5
15 15
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 1 1
5 7
1 2 1
1 5 1
2 3 7
2 5 6
3 4 1
3 5 6
4 5 1
6 15
1 2 1
1 3 1
1 4 8
1 5 2
1 6 15
2 3 10
2 4 5
2 5 2
2 6 1
3 4 1
3 5 10
3 6 2
4 5 8
4 6 2
5 6 2
7 15
1 2 1
1 3 1
1 4 8
1 5 2
1 6 15
2 3 10
2 4 5
2 5 2
2 6 1
3 4 1
3 5 10
3 6 2
4 5 8
4 6 2
5 7 2
6 9
1 2 10
1 3 3
1 5 23
2 3 12
2 6 79
3 4 4
4 5 6
4 6 1
5 6 9
7 9
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 3 1
4 5 1
6 7 1
8 12
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 3 1
4 8 1
8 5 1
6 7 1
2 6 12
2 8 30
15 20
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 1 1
1 12 10
2 13 13
3 14 19
4 15 11
15 6 13
0 0
10 7 9
7 13 18
8 11 15
9 1 19
10 1 19
11 1 18
12 4 99
13 1 18
14 1 19
15 2 199
0 0