Հանքագործներ

Կա $n$ քաղաքներից բաղկացած մի երկիր, որոնցից որոշները կապված են երկկողմանի ճանապարհներով։ Ճանապարհները ունեն տարբեր երկարություններ։ Երկրի կառավարությունը ցանկանում է ստեղծել ճանապարհային ցանց, որը կապում է բոլոր քաղաքները՝ նվազագույն ընդհանուր երկարությամբ։

Ձեզ տրված է $n$ քաղաքների և $m$ ճանապարհների մասին տեղեկություն։ Յուրաքանչյուր ճանապարհի համար տրված է երեք ամբողջ թիվ՝ $u$, $v$ և $w$, որտեղ $u$ և $v$ քաղաքների համարներն են, իսկ $w$՝ ճանապարհի երկարությունը։ Ձեր խնդիրն է գտնել բոլոր քաղաքները կապող ցանցի նվազագույն ընդհանուր երկարությունը։

Մուտք

• Առաջին տողը պարունակում է երկու ամբողջ թիվ՝ $n$ (1 ≤ $n$ ≤ 100,000) և $m$ (0 ≤ $m$ ≤ 200,000)։

• Հաջորդ $m$ տողերից յուրաքանչյուրը պարունակում է երեք ամբողջ թիվ՝ $u$, $v$ (1 ≤ $u,v$ ≤ $n$, u ≠ v) և $w$ (1 ≤ $w$ ≤ 1,000,000)։

Ելք

• Տպեք մեկ ամբողջ թիվ՝ ցանցի նվազագույն ընդհանուր երկարությունը։ Եթե հնարավոր չէ կապել բոլոր քաղաքները, տպեք «-1»։