uva10296測資B

Input:
4 6
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
1 3 2
5 8
1 2 8
1 3 5
1 4 6
2 3 5
2 5 6
3 4 5
3 5 5
4 5 8
3 16
2 1 559
3 2 335
2 1 43
2 1 438
1 2 681
2 1 243
1 3 303
3 2 425
3 2 248
1 2 481
1 2 110
1 2 701
3 1 745
1 3 269
2 1 310
2 3 417
7 86
2 1 984
3 2 724
4 3 293
5 4 507
6 5 475
7 6 320
5 2 560
3 7 903
6 7 352
4 3 368
4 7 180
5 1 267
2 5 864
1 7 475
5 1 150
5 7 91
3 4 165
7 4 988
1 2 77
7 5 377
4 1 96
7 2 829
4 5 508
4 5 976
6 2 693
5 2 797
7 4 894
7 5 227
2 4 59
2 4 334
7 4 47
7 3 651
6 3 366
1 3 647
1 4 842
7 6 225
3 7 39
7 5 396
7 5 618
7 2 909
1 5 923
2 5 838
6 5 262
7 6 214
7 1 419
7 6 699
6 4 672
5 3 473
3 1 554
6 1 681
6 7 393
6 1 529
1 7 320
2 6 462
2 5 397
6 5 576
1 2 51
4 5 610
6 4 1
7 2 260
3 6 297
6 1 638
1 6 546
4 7 441
5 1 316
1 2 48
6 1 63
1 7 148
5 4 614
4 7 284
3 2 858
7 1 741
6 1 258
7 2 361
7 6 480
7 3 258
7 6 890
6 1 289
7 3 235
3 2 847
1 4 632
7 1 230
7 4 558
7 4 450
6 2 128
5 1 768
7 67
2 1 973
3 2 458
4 3 909
5 4 490
6 5 380
7 6 790
5 1 341
5 4 4
3 2 728
5 7 344
3 5 8
4 7 544
3 4 306
4 6 145
1 6 712
2 3 371
4 2 281
5 3 708
5 3 467
5 2 841
6 3 100
1 7 246
6 4 697
3 2 474
1 3 401
2 7 599
7 4 888
1 5 267
6 7 304
2 1 809
2 7 144
2 6 677
2 6 224
1 7 550
7 6 928
6 4 671
1 3 920
1 6 274
2 4 681
4 3 358
2 4 953
5 1 598
1 6 958
7 4 656
6 5 746
6 7 290
2 1 457
2 4 758
2 1 198
3 5 359
3 6 318
1 2 279
4 7 958
6 1 156
7 2 974
6 7 28
4 2 543
5 1 543
4 7 962
1 3 460
5 6 525
2 1 828
1 6 546
6 7 386
5 3 211
2 7 466
6 2 487
0
Output:
36
60
6556
40034
34927