P20471 [HackerEarth] You have recently started playing a brand new computer game called "Mr. President". The game is about ruling a country, building infrastructures and developing it.
普及
题目描述

You have recently started playing a brand new computer game called "Mr. President". The game is about ruling a country, building infrastructures and developing it.

Your country consists of N cities and M bidirectional roads connecting them. Each road has assigned a cost of its maintenance. The greatest achievement in the game is called "Great administrator" and it is given to a player who manage to have all cities in the country connected by roads in such a way that it is possible to travel between any two cities and that the sum of maintenance costs of these roads is not greater than K.

This is very hard to accomplish, but you are very close to do it. More precisely, you have just discovered a new method of transforming standard roads into super roads, with cost of maintenance just 1, due to their extreme durability.

The bad news is that it is very expensive to transform a standard road into a super road, but you are so excited that you are going to do it anyway.

In addition, because you have a lot of other expenses, you also want to first demolish as many roads as possible in order to safe some money on their maintenance first and then start working on getting the achievement. You can demolish any road in the country and that operation does not cost you anything.

Because you want to spend the absolutely minimum money in order to get the achievement, you are interested in the smallest number of transformations of standard roads into super roads in such a way that you can do that.

Input format:

In the first line there are 3 integers N, M and K denoting the number of cities in the country, the number of roads in it and the desired sum of costs of maintenance.
M lines describing these roads follow. In each of them there are 3 integers A, B and C, where A and B denote the endpoints of the road while C denotes the cost of its maintenance.

Output:

In a single line, output the minimum number of roads which need to be transformed in order to get the achievement. If you cannot do it no matter what, output -1.

Constraints:

2 ≤ N, M ≤ 10^6
0 ≤ K ≤ 10^18
1 ≤ A, B ≤ N and A != B
1 ≤ C ≤ 10^6

SAMPLE INPUT
3 3 25
1 2 10
2 3 20
3 1 30

SAMPLE OUTPUT
1

Explanation

You can transform to super a road either the road between cities 1 and 2 or the road between cities 2 and 3 in order to produce the desired road network of costs respectively 21 and 11. Doing that will cost you one transformation and it is optimal in this case.

输入格式

见题面

输出格式

见题面

样例输入
1000 1000 456074554 1 2 655618 500 1 541659 3 2 537935 3 4 525331 4 5 486307 5 6 496295 7 6 865080 8 7 166045 8 9 67396 9 10 836804 11 10 45544 12 11 79925 12 13 338657 13 14 211546 15 14 387412 16 15 557738 16 17 495569 17 18 889412 19 18 700742 19 20 39331 21 20 886634 22 21 655708 22 23 979352 24 23 119916 25 24 125333 26 25 43046 26 27 269140 27 28 807414 29 28 814774 29 30 704920 30 31 716789 31 32 869187 32 33 380420 34 33 717523 34 35 168666 35 36 868247 37 36 291658 38 37 337171 38 39 726950 39 40 859552 41 40 367583 42 41 928500 43 42 324438 43 44 750016 44 45 466739 46 45 390329 47 46 183918 47 48 158774 49 48 545904 50 49 217221 51 50 142971 52 51 440811 53 52 669669 53 54 169563 54 55 236120 55 56 597471 56 57 785789 57 58 273217 59 58 14592 59 60 795443 60 61 800946 62 61 80141 62 63 547113 64 63 72498 64 65 211437 66 65 436223 66 67 785495 67 68 33881 69 68 63299 70 69 752647 70 71 187655 72 71 273311 72 73 16032 74 73 211694 75 74 75361 75 76 286302 76 77 78660 77 78 548897 79 78 516543 80 79 792585 81 80 902756 82 81 932388 83 82 400670 83 84 317500 85 84 384072 86 85 281736 86 87 544877 87 88 199366 89 88 952519 89 90 204947 90 91 384423 91 92 943094 93 92 23341 93 94 845425 94 95 481881 96 95 325744 96 97 787229 97 98 640061 99 98 51356 100 99 554298 100 101 538795 102 101 298163 103 102 4923 104 103 833123 105 104 303862 105 106 726835 106 107 708599 107 108 521327 108 109 639979 110 109 284502 110 111 737967 111 112 979003 113 112 842463 113 114 621297 115 114 193712 115 116 529069 117 116 549617 118 117 451342 119 118 212936 120 119 419077 120 121 42822 121 122 955197 123 122 218920 124 123 682719 125 124 144720 126 125 323833 127 126 365531 128 127 431475 128 129 988733 130 129 952008 130 131 66046 131 132 832754 133 132 420928 134 133 642563 135 134 484424 135 136 616532 137 136 206175 138 137 124734 138 139 705090 140 139 818535 141 140 942238 142 141 568724 142 143 977292 143 144 354981 144 145 691893 146 145 198869 147 146 250872 148 147 632860 148 149 67375 150 149 110552 150 151 898075 152 151 615290 153 152 346105 154 153 145188 154 155 858212 155 156 560194 157 156 301241 158 157 301908 159 158 207841 159 160 300084 160 161 901496 161 162 854096 162 163 700818 163 164 481120 164 165 226786 165 166 788520 167 166 295478 167 168 116723 169 168 807382 170 169 172496 170 171 908794 171 172 738970 172 173 281580 173 174 558221 174 175 583459 175 176 352514 176 177 898410 178 177 754135 179 178 13867 180 179 970182 181 180 158947 181 182 79803 182 183 592800 183 184 659875 184 185 705120 185 186 96986 187 186 411198 188 187 485825 188 189 391593 189 190 14818 190 191 418507 191 192 485791 193 192 20308 193 194 446780 194 195 362552 196 195 840185 196 197 121344 197 198 92635 199 198 392602 200 199 839029 201 200 348546 201 202 663671 203 202 762260 204 203 509354 204 205 908712 205 206 878733 206 207 632612 207 208 780146 209 208 354985 210 209 741253 211 210 818697 212 211 85006 213 212 950885 213 214 703571 215 214 901180 215 216 343900 216 217 414737 218 217 30643 218 219 544019 220 219 1255 221 220 627019 221 222 546830 222 223 1116 223 224 852855 224 225 576439 225 226 457730 227 226 532150 227 228 453318 228 229 467796 229 230 710692 230 231 77021 232 231 983405 233 232 216374 233 234 743181 234 235 416623 235 236 634610 237 236 9203 237 238 924434 238 239 736198 239 240 884999 241 240 961480 242 241 412635 242 243 174461 244 243 274020 244 245 336441 245 246 412414 247 246 407093 248 247 13654 249 248 386502 249 250 456702 251 250 997262 251 252 957511 252 253 309911 254 253 9113 254 255 858352 256 255 652724 256 257 894922 258 257 528984 258 259 218292 260 259 894934 260 261 762705 261 262 625310 262 263 233745 263 264 111136 264 265 911999 266 265 172112 266 267 491600 267 268 193583 269 268 623943 270 269 458412 270 271 913884 271 272 234211 273 272 148489 274 273 583659 274 275 627573 275 276 57898 277 276 199947 277 278 726399 279 278 323530 280 279 209051 280 281 730619 282 281 669195 282 283 15621 284 283 133096 285 284 608167 285 286 270116 286 287 28301 287 288 926390 289 288 405958 290 289 285957 291 290 282592 291 292 709925 292 293 159256 294 293 612047 295 294 527619 296 295 22297 296 297 142059 297 298 901140 298 299 79508 300 299 956307 300 301 481756 301 302 188331 303 302 427493 304 303 420016 304 305 25379 305 306 445505 307 306 680631 307 308 564486 309 308 687950 310 309 704272 310 311 772278 312 311 379674 312 313 729058 313 314 370250 314 315 626060 316 315 501573 316 317 961163 318 317 690412 318 319 907814 320 319 389251 320 321 675714 321 322 795510 322 323 538931 324 323 586966 324 325 664291 325 326 872383 327 326 178089 328 327 334504 329 328 378989 330 329 991481 330 331 527903 331 332 258462 333 332 609146 334 333 704739 335 334 476405 335 336 539379 337 336 651123 338 337 959422 338 339 84573 340 339 71020 340 341 451625 341 342 319643 343 342 270582 343 344 284964 345 344 624259 345 346 342541 346 347 576358 347 348 370491 349 348 955525 350 349 990422 351 350 263216 351 352 702630 352 353 972529 353 354 893405 355 354 405021 356 355 340968 357 356 571978 357 358 116714 358 359 596631 359 360 883778 361 360 366680 362 361 402816 363 362 639264 363 364 735355 365 364 800759 366 365 741671 366 367 111672 367 368 47955 369 368 520583 370 369 616481 370 371 981211 371 372 987677 373 372 353834 373 374 382646 375 374 474137 375 376 571603 377 376 889950 377 378 704082 378 379 416078 380 379 312156 381 380 287039 381 382 487718 382 383 340377 384 383 929775 384 385 562775 385 386 450014 387 386 350232 387 388 794332 389 388 229810 389 390 980983 391 390 908438 391 392 9111 393 392 895349 393 394 640364 394 395 800893 396 395 974366 397 396 205894 398 397 454743 399 398 419880 400 399 674253 401 400 802384 402 401 736696 403 402 879632 403 404 107856 405 404 458532 406 405 849392 407 406 966967 408 407 665498 408 409 648076 409 410 564035 411 410 2999 412 411 72451 412 413 699233 414 413 422147 414 415 521406 415 416 547923 417 416 388398 417 418 30161 419 418 529206 420 419 176661 421 420 538435 422 421 920356 422 423 418723 424 423 587304 424 425 178529 425 426 612140 427 426 724775 428 427 919635 428 429 628307 429 430 685161 431 430 123022 431 432 49494 432 433 929419 433 434 179582 434 435 977252 435 436 926388 436 437 189268 438 437 270006 439 438 651529 440 439 135417 440 441 560384 442 441 149626 442 443 885929 443 444 661744 445 444 689982 445 446 218581 447 446 141357 448 447 989068 448 449 15830 449 450 39721 451 450 771770 451 452 973532 453 452 159596 453 454 438312 455 454 374526 455 456 361038 456 457 950674 458 457 495474 459 458 806550 459 460 785764 461 460 695662 462 461 448619 463 462 280724 463 464 499164 465 464 203241 466 465 226685 467 466 512555 467 468 944019 469 468 537917 469 470 459473 471 470 866332 472 471 561104 473 472 444192 474 473 196854 474 475 173643 476 475 136986 477 476 230333 478 477 978222 478 479 735171 479 480 383480 480 481 25592 481 482 802381 482 483 989119 483 484 596261 485 484 806371 486 485 984649 486 487 544603 488 487 295338 489 488 688789 490 489 498608 491 490 891310 491 492 159959 492 493 449314 494 493 698689 494 495 157515 496 495 513679 496 497 844658 498 497 531906 498 499 58000 499 500 597381 502 501 713577 1000 501 142760 502 503 59216 503 504 315241 504 505 882378 506 505 125806 507 506 865251 507 508 274768 508 509 497788 510 509 469159 511 510 893086 511 512 754422 512 513 63385 513 514 233569 514 515 9922 515 516 753059 516 517 172888 517 518 705437 518 519 203078 519 520 969267 521 520 665830 521 522 80359 522 523 854967 524 523 70432 524 525 829044 525 526 427645 526 527 147291 528 527 90012 529 528 423779 529 530 627476 530 531 977820 532 531 537297 533 532 663432 533 534 385513 535 534 607877 535 536 564532 537 536 850997 537 538 187015 538 539 618104 539 540 217210 540 541 745111 542 541 315755 542 543 50390 543 544 977721 545 544 478765 546 545 912179 547 546 499729 548 547 267655 549 548 97883 550 549 216236 550 551 526351 551 552 466768 552 553 469591 554 553 638278 555 554 197579 555 556 779826 557 556 945936 557 558 287873 559 558 204284 559 560 482205 561 560 931131 562 561 354745 562 563 451649 563 564 207166 564 565 368144 566 565 548443 566 567 314791 568 567 528004 568 569 239773 570 569 828776 571 570 434150 571 572 270828 573 572 983354 573 574 719014 574 575 862973 575 576 222834 577 576 954887 577 578 118902 579 578 710282 580 579 31652 581 580 411145 581 582 356719 583 582 422157 584 583 614302 585 584 2222 585 586 271509 587 586 412064 588 587 673119 588 589 105271 589 590 941598 590 591 18939 591 592 618299 593 592 972287 594 593 450054 595 594 579395 595 596 948457 597 596 444614 598 597 721675 598 599 873651 600 599 184926 601 600 176246 602 601 71273 603 602 905309 604 603 106818 604 605 84278 606 605 384568 606 607 334186 607 608 784257 609 608 419379 609 610 806842 611 610 923005 611 612 949036 613 612 830777 614 613 15758 615 614 886503 616 615 239954 616 617 468274 617 618 473179 618 619 662074 620 619 342795 620 621 930062 621 622 769183 622 623 589506 623 624 342947 625 624 579112 626 625 819339 627 626 673643 628 627 636844 628 629 247776 630 629 830265 631 630 206327 631 632 683942 633 632 231392 634 633 189466 635 634 608882 635 636 675214 636 637 860865 637 638 473229 639 638 35600 640 639 604677 640 641 950066 641 642 189169 642 643 859422 643 644 967618 645 644 502037 645 646 638869 647 646 881872 647 648 684254 649 648 887787 650 649 229920 650 651 768051 651 652 631571 653 652 458301 653 654 764876 654 655 421919 656 655 13258 656 657 524137 658 657 190219 659 658 905152 660 659 969290 661 660 339358 662 661 952677 662 663 941237 663 664 207923 665 664 313180 665 666 893271 666 667 36584 668 667 852258 669 668 843069 670 669 931827 670 671 898465 672 671 535949 673 672 733310 673 674 253721 674 675 850707 676 675 577130 676 677 166814 677 678 320348 679 678 870898 680 679 624434 681 680 288206 681 682 153266 682 683 866267 683 684 421525 684 685 670257 686 685 284563 687 686 746645 688 687 769656 688 689 938000 690 689 842188 691 690 271897 691 692 837982 692 693 193636 693 694 715438 694 695 342808 696 695 274955 697 696 397500 697 698 449695 699 698 838264 700 699 951141 701 700 826336 702 701 593444 703 702 418131 703 704 860068 704 705 629617 705 706 392061 707 706 322847 707 708 944191 709 708 503723 710 709 208569 711 710 61293 712 711 486144 712 713 999076 714 713 13882 714 715 492888 715 716 742818 717 716 539772 718 717 440882 718 719 392661 719 720 971115 721 720 209703 722 721 734169 723 722 350549 724 723 858646 724 725 980613 726 725 874403 726 727 782919 728 727 626974 729 728 839670 730 729 866950 731 730 305213 731 732 184298 732 733 485106 733 734 117484 734 735 314115 736 735 610526 736 737 615175 738 737 319714 739 738 634365 740 739 558150 741 740 871404 741 742 297067 743 742 914740 744 743 133259 744 745 302532 746 745 10448 747 746 773068 748 747 886510 749 748 846209 750 749 92334 750 751 430216 751 752 418830 752 753 449196 753 754 597790 754 755 691984 756 755 360499 757 756 294984 758 757 677369 759 758 784736 759 760 735853 761 760 787131 762 761 758618 762 763 706074 763 764 85352 764 765 212648 766 765 946148 767 766 886695 767 768 158251 768 769 674271 770 769 954982 770 771 399640 772 771 396982 772 773 135172 773 774 257332 775 774 785482 775 776 559177 777 776 497863 778 777 736433 779 778 138603 780 779 493028 781 780 182960 781 782 68867 783 782 948937 784 783 764143 785 784 794782 786 785 120694 787 786 373588 788 787 544181 788 789 923676 789 790 511503 791 790 690572 792 791 530029 792 793 578275 794 793 758490 795 794 734556 795 796 718163 796 797 632538 797 798 973339 799 798 647717 800 799 24714 800 801 755981 802 801 702496 802 803 187404 803 804 617041 805 804 316085 806 805 35741 807 806 707941 808 807 682524 808 809 55443 809 810 204953 810 811 558566 812 811 573738 813 812 804535 813 814 895430 815 814 916183 815 816 589040 817 816 122738 818 817 577136 819 818 11153 820 819 84853 821 820 42116 821 822 118651 823 822 689547 824 823 905687 825 824 741412 826 825 940316 827 826 438103 827 828 158417 828 829 374433 830 829 244275 831 830 460489 831 832 806704 833 832 83523 833 834 177986 835 834 254258 835 836 938757 836 837 293317 837 838 563967 839 838 205380 839 840 816819 841 840 384953 841 842 510609 842 843 310068 843 844 794551 845 844 397225 846 845 754539 847 846 689683 847 848 957585 848 849 213740 850 849 390272 850 851 417152 852 851 868862 853 852 545057 853 854 622870 854 855 76620 855 856 408477 856 857 947047 857 858 481765 858 859 692662 860 859 815625 860 861 666654 862 861 480111 862 863 521750 864 863 580750 864 865 599556 865 866 51451 866 867 118717 867 868 709914 869 868 532270 870 869 162002 870 871 458875 872 871 253287 872 873 465711 874 873 673888 875 874 905471 876 875 577198 876 877 74860 878 877 953039 878 879 837234 879 880 277037 881 880 573777 882 881 912466 883 882 496695 884 883 746357 884 885 171794 885 886 606882 887 886 155197 887 888 517382 889 888 982133 889 890 180472 890 891 677646 892 891 540804 893 892 930878 894 893 246221 894 895 909612 895 896 158034 897 896 999563 898 897 827057 899 898 491961 899 900 793532 900 901 241022 902 901 283752 902 903 30453 903 904 1228 905 904 960887 905 906 486186 906 907 8203 907 908 285396 908 909 921561 909 910 906269 911 910 265675 912 911 258761 913 912 336592 914 913 739264 914 915 397902 916 915 263643 917 916 89242 918 917 947184 918 919 141282 919 920 938019 921 920 494814 922 921 751548 922 923 891914 923 924 991904 924 925 623820 926 925 553657 927 926 330727 928 927 849569 928 929 643003 930 929 858862 931 930 345256 931 932 370350 932 933 474077 934 933 924585 935 934 783046 935 936 24565 937 936 777364 937 938 287176 938 939 924581 939 940 294772 941 940 439245 942 941 474505 942 943 423612 943 944 306410 944 945 26680 946 945 631082 947 946 880436 947 948 341278 949 948 46762 949 950 701114 951 950 492650 951 952 499925 953 952 740894 954 953 553410 955 954 282708 956 955 213632 957 956 462719 957 958 260310 959 958 283826 960 959 785128 961 960 700051 961 962 283180 963 962 443630 963 964 703929 965 964 129860 965 966 70892 966 967 258718 968 967 808889 968 969 236510 970 969 357544 971 970 106145 971 972 516893 973 972 808637 974 973 197439 974 975 276906 976 975 857320 977 976 958947 978 977 70969 979 978 319391 979 980 196050 980 981 885564 982 981 397032 983 982 856402 983 984 401261 985 984 136876 985 986 30310 986 987 209500 988 987 106450 989 988 897605 989 990 883536 991 990 461418 991 992 40268 993 992 469284 994 993 521573 995 994 371409 996 995 328212 996 997 952857 997 998 683616 998 999 939035 999 1000 285588
样例输出
214