Կողի հեռացում

Տրված է N գագաթ և M կող ունեցող կշռված, պարզ(*), կապակցված, ոչ ուղղորդված գրաֆ G։ Գագաթները համարակալված են 1-ից N հաջորդական ամբողջ թվերով, կողերը՝ 1-ից M հաջորդական ամբողջ թվերով։ i-րդ կողը միացնում է $u_i$ և $v_i$ ($u_i ≠ v_i$) գագաթները և նրա կշիռը $w_i$ է:

X ենթագրաֆի համար W(X)-ով նշանակենք X-ում ընկած կողերի կշիռների գումարը։

Ձեր խնդիրն է ջնջել գրաֆից մի կող այնպես, որ առաջացած A և B կապակցված կոմպոնենտների համար (եթե գրաֆը մնում է կապակցված, ապա համարել, որ B = Ø, W(Ø) = 0) |W(A) – W(B)| արտահայտության արժեքը լինի նվազագույնը։

Եթե պայմանին բավարարող կողերը շատ են, ընտրել այն մեկը, որի դեպքում $u_i$-ն ամենափոքրն է։ Եթե էլի պատասխանը միանշանակ չէ, վերջիններից ընտրել այն կողը, որի դեպքում $v_i$-ն ամենափոքրն է։

(*) Հիշեցում՝ պարզ է կոչվում այն գրաֆը, որը չունի կրկնվող կողեր և գագաթը ինքն իրեն միացնող կողեր։

Մուտքային տվյալներ

Առաջին տողում տրված են N և M ամբողջ թվերը։ Հաջորդ M տողերից յուրաքանչյուրը նկարագրում է գրաֆի մի կող՝ $u_i$, $v_i$ և $w_i$ ամբողջ թվերով (1 ≤ ui, vi ≤ N, ui ≠ vi, 1 ≤ wi ≤ 109), որտեղ $u_i$-ն և $v_i$-ն կողով միացվող գագաթների համարներն են, $w_i$-ն՝ կողի կշիռը։ Երաշխավորվում է, որ ոչ մի $(u_i, v_i)$ չկարգավորված զույգ չի կրկնվում, և որ գրաֆը կապակցված է։

Ելքային տվյալներ

Հարկավոր է արտածել երկու թիվ՝ կողի գագաթների համարները։

Օրինակ

Աղբյուրը. Հանրապետական 2019