input:

6 11
1 2 23
1 3 12
1 4 99
2 5 17
2 6 73
3 5 3
3 6 21
4 6 8
5 2 33
5 4 5
6 5 20
6 14
1 2 1
2 1 1
1 3 2
3 1 2
3 4 2
4 3 2
2 4 1
4 2 1
2 5 2
5 2 2
4 6 1
6 4 1
5 6 2
6 5 2
3 3
1 3 1
1 2 5
2 3 5
4 4
1 2 10
1 3 15
2 4 16
3 4 17
6 8
1 2 10
1 3 15
2 4 13
2 5 30
3 4 32
3 5 16
4 6 16
5 6 17
8 10
1 2 10
1 3 15...

output:

86
10
11
58
87
247
352
298
392
201
323
283
271
265
275
234
210
985
1484
8058
14510
39235

result:

ok 22 lines