事情發生在跑跑卡恩車大賽後的幾個月…(請參考TIOJ-1022)

　　經過了跑跑卡恩車大賽後，原本居住在上城的寒酸員外老姜跟原本居住在下城強大的科學家老皮與老灝成為了好朋友，感情好到常常聚在一起打賭（賭友是嗎？）
　　有一天老姜邀請老皮與老灝一同到家裡作客，並在信中誇耀自己有多有錢，比魏晉的石崇當年使用紫絲屏障還奢華，可以讓自己踩著絲製地毯（卡恩國由於天氣關係不適合養蠶等產絲動物，所以價錢十分昂貴）遍遊他所居住的小鎮中所有的觀光景點，老皮與老灝十分懷疑，於是發明了『絲製布料偵測鞋』（就說是強大的科學家咩），並前往老姜家中。

　　當老姜看到老灝與老皮提著那雙『絲製布料偵測鞋』過來時，他的心涼掉了半截，他哪有這麼多錢呢？於是沒有辦法，只能能省則省了！
　　身為老姜家會計的你，為了拯救老姜的信用，也為了家裡的開銷，決定自己找出如何才能花費最少的錢完成任務（畢竟老姜年紀大了，腦袋不好信任），於是你上網查了地圖跟一些相關資料，所以你知道：

1.老姜住的小鎮名叫做正派鎮（不是真新鎮），是個面積宛如大國般的小鎮（卡恩國國土十分廣闊，就連一個小鎮也可以很大很大），而且住在那兒的人都非常正派，絕對不糟糕。
2.正派鎮中有n個觀光景點，各有各的名字。(1<=n<=50)
3.正派鎮中有m條路，連接兩個觀光景點，各有名字以及長度。
4.觀光景點上會有可愛的服務小妹妹幫你在觀光手冊上蓋章，所以老灝與老皮可以知道你到底有沒有到那裡。
5.由於老灝與老皮太過強大，『絲製布料偵測鞋』不可能出錯，所以只要腳一踏到非絲製布料時，老灝與老皮馬上就會知道。
6.由於卡恩國國庫十分充足，所以觀光景點上總是覆滿著絲製地毯，但是也沒有富有到哪裡去，所以並沒有將道路鋪設地毯。
7.最近物價上漲，原本一單位長度只要66TMT幣的地毯，居然漲到了100TMT幣（TMT幣的幣值非常非常高）
8.老姜祖先還滿有錢的，所以他住在某一個觀光景點上的別墅。
9.我們翻閱地圖發現景點與道路的名稱都不會超過30個字元

但是由於道路實在過於錯綜複雜，所以你決定寫個程式來找出最好的方法！
寫完之後，你就可以幫助老姜脫離困境了！