Şəbəkə müharibələri
Sistem Baitlandiyada n serverdən və m optik kabellərdən ibarətdir. Hər bir kabel iki serveri birləşdirir və məlumatları hər iki istiqamətdə ötürə bilir. Şəbəkədə iki server xüsusilə vacibdir - biri qlobal dünya şəbəkəsinə, digəri isə prezident sarayının şəbəkəsinə qoşulub.
Prezident sarayının şəbəkəsinə qoşulan serverin nömrəsi 1, qlobal dünya şəbəkəsinə qoşulan serverin nömrəsi isə n-dir.
Son zamanlarda Maks Trafik şirkəti bəzi kabelləri nəzarət altına almağa qərar verib ki, prezident sarayının istifadəçiləri tərəfindən ötürülən məlumatları izləyə bilsin. Onlar elə bir kabel dəstini nəzarət altına almaq istəyirlər ki, qlobal şəbəkədən prezident sarayına heç bir məlumat ötürülə bilməsin, ən azı həmin dəstdən bir kabel vasitəsilə ötürülmədən.
Planlarını həyata keçirmək üçün şirkət həmin kabelləri onların hazırkı sahiblərindən almalıdır. Hər bir kabelin müəyyən bir qiyməti var. Şirkətin əsas işi casusluq deyil, ev istifadəçilərinə internet bağlantısı təmin etmək olduğundan, rəhbərlik əməliyyatı yaxşı bir sərmayə etmək istəyir. O, elə bir kabel dəsti almaq istəyir ki, onların orta qiyməti mümkün olan ən minimal olsun.
Beləliklə, əgər şirkət ümumi dəyəri c olan k kabel alırsa, o, c / k qiymətini minimallaşdırmaq istəyir.
Giriş məlumatları
Birinci sətir n və m dəyərlərini ehtiva edir (2 ≤ n ≤ 100, 1 ≤ m ≤ 400). Növbəti m sətir kabelləri təsvir edir - hər bir kabel üç tam ədədlə verilir: birləşdirdiyi serverlərin nömrələri və kabelin qiyməti. Hər bir kabelin qiyməti müsbətdir və 10^7-dən çox deyil.
İstənilən iki server bir kabeldən çox birləşdirilmir. Heç bir kabel serveri öz-özünə birləşdirmir. Şəbəkə əlaqəlidir, istənilən iki server arasında məlumat ötürmək mümkündür.
Çıxış məlumatları
Alınmalı olan kabellərin sayını k çıxarın. Sonra alınan kabellərin nömrələrini çıxarın. Kabellər girişdə verildiyi sırayla birdən başlayaraq nömrələnir.