SPOJ in Armenian

Տրված է 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 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ w_i ≤ 10⁹), որտեղ u_i-ն և v_i-ն կողով միացվող գագաթների համարներն են, w_i-ն՝ կողի կշիռը։ Երաշխավորվում է, որ ոչ մի (u_i, v_i) չկարգավորված զույգ չի կրկնվում, և որ գրաֆը կապակցված է։

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

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

Օրինակ

Մուտք
10 11
1 2 1
2 3 10
1 5 2
3 4 7
3 5 9
5 6 8
6 7 5
6 8 3
7 8 12
7 9 1
9 10 8

Ելք
5 6