Условие

---

ГРУПА A. ЗАДАЧА C. СВЪРЗАНИТЕ СЕЛА
---
Имало едно време в далечна земя група села, разделени от гъсти гори и дълбоки реки. Селата нямали средства за комуникация и търговия и всяко село се самоиздържало, но хората копнеели за по-добър живот.

Един ден мъдър старец дошъл в селата и говорил със старейшините. Той им разказал за чудесата на търговията и как може това да им донесе просперитет. Но той също така обяснил, че за да се осъществи търговията, селата трябва да бъдат свързани и единствения начин да стане това е да се построят пътища през горите и мостове над реките.

Старейшините били убедени и решили да работят заедно за изграждането на пътища и мостове. Скоро обаче те осъзнали, че нямат достатъчно ресурси, за да построят всички пътища и мостове, които били необходими, и не знаели въобще откъде да започнат.

Помогнете на хората като напишете програма, която да им помогне да идентифицират минималния брой пътища, които трябва да построят, за да свържат всички села.Алгоритъмът трябва да намира минималното обхващащо дърво на пътната мрежа на селата.

Така селата ще бъдат свързани и търговията ще процъфтявала. Хората ще Ви бъдат благодарни за Вашата помощ и ще се радват на просперитета, който ще дойде с техния новосвързан свят. От този ден нататък селата вече не са изолирани и ще станат известни като Свързаните села, ярък пример за силата на сътрудничеството и технологиите.

Вход:
На първият ред на стандартния вход се въвеждат две цели числа: N и E, които съответсват на броя на селата и броя на пътищата между тях, разделени с един интервал. Следващите E на брой редове съдържат по три цели числа: U,V,W, които съотвестват на път от село U до село V с дължина W.

Изход:
На стандартният изход програмата трябва да намери и изведе минималното обхващащо дърво на пътната мрежа на селата.

Примерен вход:
7 8
1 3 1
1 4 2
2 3 3
2 4 4
2 5 5
5 6 6
6 7 7
3 6 8	

Примерен изход:
1 3
1 4
2 3
2 5
5 6
6 7

Пояснение на примерният вход:
    4 -- 2 -- 5
   /|\    |\  |
  1 | \   | \ |
   \|  \  |  \|
    3 -- 6 -- 7