Tək kəsik#5467
Verilmiş bağlı yönsüz qrafda zirvə və kənar var. Hər bir kənara qeyri-mənfi tam çəki verilib. Məlumdur ki, təkdir. Tapşırığınız zirvələri və çoxluqlarına elə bölməkdir ki, aşağıdakı şərtlər ödənsin:
və bir-birindən fərqli, birlikdə bütün zirvələri əhatə edən çoxluqlar olsun.
Hər iki çoxluğun və tutumu tək sayda olsun.
Bir ucu -da, digər ucu -də olan kənarların çəkilərinin cəmi minimal olsun.
Birinci sətirdə iki tam ədəd — və (1 \leq n \leq 200, 1 \leq m \leq 2000) verilir. Növbəti sətrdə qrafın kənarları təsvir olunur. Hər sətirdə üç tam ədəd var — kənarın uclarının nömrələri və çəkisi (bu, -dan 10^5-ə qədər (daxil olmaqla) tam ədəddir). Qrafın zirvələri birinci ilə nömrələnir. Qrafda döngələr yoxdur, lakin çoxlu kənarlar ola bilər.
Birinci sətirdə müxtəlif çoxluqlarda ucları olan kənarların minimal cəmi çəkisini çap edin. İkinci sətirdə çoxluğunun tutumunu çap edin. Üçüncü sətirdə həmin çoxluğa daxil olan zirvələrin nömrələrini çap edin.
Nümunə 1