За време на регионалниот натпревар по информатика, можно е да се случи прекин на интернет врската (на пример, има прекин на електричната енергија поради поплава врз инсталацијата).

Во тој случај, ЗИМ треба брзо да ги извести натпреварувачите за новата IP адреса на серверот. Знаејќи дека некои од натпреварувачите се познаваат меѓу себе и можат да комуницираат со мобилни телефони, Комисијата заклучила дека е доволно да извести еден натпреварувач, кој понатаму може да ги извести неговите пријатели, итн.

Комуникацијата помеѓу натпреварувачите (преку телефон) се плаќа, и цената може да е различна помеѓу секои двајца кои комуницираат заради тоа што некои натпреварувачи се позборливи, како и поради различните оператори, различните тарифи, итн.

Комисијата сака да утврди начин за ширење на информацијата кој што е најефтин.

Нека ви се дадени цените за комуникација за некои парови натпреварувачи (останатите натпреварувачи не комуницираат меѓусебно). Вие треба да ја дадете најниската можна цена на комуникација за информирање на сите натпреварувачи (комуникацијата помеѓу А и B чини исто како комуникацијата помеѓу B и А). Дополнително, (за секој случај) дадете ја и цената на помошниот план за комуникација (втората најниска цена). Помошниот план треба да се разликува од главниот во барем еден разговор помеѓу натпреварувачите (треба да постои барем еден разговор помеѓу двајца натпреварувачи во првиот план, кој не постои во вториот план).

Влез

Во првата линија од влезот се запишани два цели броеви одвоени со празно место, N (3 <= N <= 100) - бројот на натпреварувачи и M – бројот на можни парови натпреварувачи кои би комуницирале (2 <= M <= 500). Во следните M линии се дадени по 3 броја Ai, Bi и Ci, каде Ci (1 <= Ci <= 300) ја означува цената на комуникацијата помеѓу натпреварувачите Ai и Bi (1 <= Ai, Bi <= N). Натпреварувачите се означени со броеви од 1 до N.

Излез

На стандарден излез, во еден ред одделени со празно место, отпечатете ги бараните две најниски цени (секогаш ќе постои решение). Доколку цените се различни, како прва вредност отпечатете ја пониската цена. И во случај цените да се исти, пак треба да ги отпечатите и двете.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5 6
3 4 51
4 2 19
5 4 30
1 2 7
3 2 95
5 2 40

излез
107 117

Објаснување: Постојат повеќе можни сценарија кои ќе доведат до цена 107. Едно е да го информираме натпреварувачот 2, кој ќе ги информира 4 (за цена 19) и 1 (за цена 7). Понатаму, 4 ќе ги информира 5 (за цена 30) и 3 (за цена 51). Во вториот план – нема разговор помеѓу 4 и 5, но затоа 5 е информиран од страна на 2.