Дзи физикт дуртай. Тэр нягтыг тооцон бодох дуртай.

Бараг бүх зүйлд нягт байдаг, графад ч бас. Чиглэлт бус графын нягтыг дараах байдлаар тодорхойлъё: (графын ирмэг болон орой нь ямар нэгэн утгатай байдаг)

Энд $v$ бол оройнуудын нийлбэр, $e$ бол ирмэгүүдийн нийлбэр.

Дзид $G$ граф байв. Одоо тэр уг графын дэд граф болдог, холбоотой граф $G'$-г олохыг хүсч байна. Энд $G'$-ийн нягт аль болох их байна.

$G(V, E)$ графын $G'(V', E')$ дэд граф нь дараах нөхцөлүүдийг хангасан байна. Үүнд:

• ;
• Хэрэв ба ирмэг байвал ирмэг байна;
• $G'$ дэх ирмэгийн утга харгалзах $G$ дэх ирмэгийн утгатай ижил бол энэ нь зангилааны утга болно.

Дзид хамгийн их нягтралтай дэд графыг олоход туслаарай. Таны олсон дэд граф холбоотой байх ёстой гэдгийг анхаараарай.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n (1≤n≤500)$, 2 бүхэл тоог агуулна. $n$ бүхэл тоо нь $G$ графын зангилааны тоо, $m$ нь ирмэгийн тоог харуулна.

Дараагийн мөр нь $n$ ширхэг, зайгаар тусгаарлагдсан $x_{i} (1≤x_{i}≤10^{6})$ бүхэл тоонуудыг агуулна. Энд, $x_{i}$ нь $i$-р зангилааны утгыг харуулна. Графын зангилаануудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.

Дараагийн $m$ мөрүүд тус бүр нь зайгаар тусгаарлагдсан $a_{i}, b_{i}, c_{i} (1≤a_{i}

Гаралт

Хариуг дүрслэх, харьцангуй болон үнэмлэхүй алдаа нь хамгийн багадаа $10^{ - 9}$ байх бодит тоог хэвлээрэй.

Эхний жишээнд, та хоосон эсвэл зөвхөн $1$ зангилаатай дэд графыг сонгож болох юм.

Хоёр дахь жишээнд графыг бүхлээр нь сонгох хэрэгтэй.