uva10296測資A

Input:
4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
4 6
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
2 4 20
8 22
2 1 355
3 2 712
4 3 231
5 4 939
6 5 293
7 6 671
8 7 520
3 5 727
7 6 153
3 1 301
7 3 43
2 7 46
1 7 404
2 1 368
8 4 55
3 6 320
2 6 424
8 3 120
2 7 851
7 5 307
8 2 629
7 3 367
5 87
2 1 640
3 2 985
4 3 389
5 4 130
2 3 368
2 4 930
1 4 568
2 3 33
1 3 601
5 4 341
2 4 281
2 5 868
4 3 642
3 5 843
1 4 336
5 2 746
2 1 155
2 4 8
5 2 9
5 4 469
2 4 456
3 1 631
5 3 51
3 5 13
4 3 394
1 4 82
1 3 138
2 4 464
2 4 383
5 4 397
3 4 394
5 1 869
5 2 162
4 1 976
3 4 313
5 3 815
2 1 822
1 4 795
1 5 842
3 1 317
3 5 828
1 5 642
1 3 84
2 3 557
5 1 65
2 5 129
3 5 271
3 4 122
3 4 246
2 1 567
2 3 312
5 1 564
3 1 997
5 1 224
4 2 658
4 2 231
3 2 509
2 3 961
5 2 823
5 2 37
5 4 629
3 2 474
4 3 552
4 3 217
2 4 688
3 1 267
4 5 403
3 2 525
2 5 777
4 1 862
1 3 86
3 1 25
2 1 82
5 2 774
2 4 48
3 5 435
2 1 362
2 3 203
5 4 630
2 5 460
1 5 856
4 3 867
5 2 440
5 3 183
3 4 410
4 3 200
2 4 111
8 77
2 1 839
3 2 734
4 3 111
5 4 771
6 5 319
7 6 993
8 7 318
2 4 237
8 4 446
2 5 602
7 5 907
1 2 658
3 2 829
8 2 327
1 5 554
7 3 850
4 5 267
4 3 826
2 6 692
6 1 451
3 5 18
2 5 925
7 6 980
1 4 914
8 4 949
5 1 567
6 7 598
1 7 151
8 2 259
2 8 612
1 7 384
7 1 126
3 2 294
8 1 635
2 4 576
5 7 11
3 1 101
5 4 328
6 8 723
7 2 67
6 4 131
8 7 759
1 6 442
5 7 734
5 3 350
4 1 609
8 1 641
4 8 935
1 8 296
4 8 446
3 2 376
3 4 166
6 1 271
8 5 858
6 2 8
1 6 173
8 4 932
8 2 487
2 3 37
2 6 675
2 7 813
6 5 212
4 2 995
8 7 968
4 3 414
7 3 478
4 6 804
6 1 650
6 3 627
2 8 462
1 6 841
2 8 599
2 1 610
3 7 898
3 8 879
2 5 611
7 2 327
0
Output:
41
62
9253
39062
41574