SPOJ in Armenian

Երկրում կա N քաղաք, յուրաքանչյուր քաղաք թողարկում է M ապրանքներից որևէ մեկը։ Միևնույն ապրանքը թողարկող քաղաքները կոչվում են մրցակից քաղաքներ։ Երկրի քաղաքները ուզում են միավորել առևտրական ցանցի մեջ։  Ցանց կազմելու համար անհրաժեշտ է քաղաքներն իրար միացնել ճանապարհների այնպիսի ցանցով, որ ցանկացած  A քաղաքից հնարավոր լինի գնալ ցանկացած B քաղաքը։ Ընդ որում, այդ ցանցում մրցակից քաղաքներն իրար հարևան լինել չեն կարող։

Ձեր խնդիրն է տրված քաղաքների համար կառուցել ճանապարհների այնպիսի ցանց, որի երկարությունը լինի մինիմալ։ Ցանցի երկարությունը կառուցված ճանապարհների երկարությունների գումարն է։ Ճանապահները պետք է ուղղագիծ լինեն։ Ճանապարհները քաղաքներից դուրս հատումներ չպիտի ունենան։ Համարել, որ անհրաժեշտության դեպքում նրանք հատումներից խուսափելու համար անցնում են տարբեր մակարդակներով։

Մուտք

Մուտքի առաջին տողում տրված են N և M թվերը (1 ≤ N ≤ 200, 1 ≤ M ≤ 200)։ Հաջորդ N տողերում նկարագրված են քաղաքները, յուրաքանչյուր քաղաքի նկարագրություն զբաղեցնում է մեկ տող և բաղկացած է մեկական բացակով իրարից անջատված երեք ամբողջ թվերից՝ Xi, Yi, Zi, որտեղ  Xi–ն և Yi–ն  i-րդ քաղաքի կոորդինատներն են, իսկ Zi –ն այդ քաղաքում թողարկվող ապրանքի համարն է (-10000 <= X_i , Y_i <= 10000, 1 <= Z_{i <=} M, 1 <= i <= N)։

Ելք

Ելքի միակ տողում հարկավոր է արտածել մի իրական թիվ մինչև 0.001 ճշգրտությամբ՝ ճանապարհների ցանցի մինիմալ երկարությունը։

Եթե քաղաքները հնարավոր չէ միավորել առևտրական ցանցի մեջ, հարկավոր է արտածել -1։

Օրինակ

Մուտք.
8 3
3 3 1
3 10 1
5 6 2
10 6 3
10 10 2
15 3 1
15 6 3
15 10 2

Ելք.
29.909