DER UNTERGANG - 費格萊茵

題目敘述

「嗨元首」醫生對著進來的元首行納粹禮，元首緩緩地走進來「你要求離開柏林？」「元首，您知道，黨衛軍和希姆萊手下的所有醫療部隊，都已經離開柏林」「希姆萊是個叛國者，他逃脫不了懲罰的」元首已經氣瘋了，「元首，作為黨衛軍的醫生，我在這裡已經無事可做了」醫生顫抖的說著，「你想要離開柏林的要求是完全不能接受的」元首堅定的否決，「我..我的家人...如果俄國人...我必須離開」「你沒做錯什麼，後輩們會感謝你所做的醫學研究，我會承擔全部的責任」元首揮了揮手「下次再談吧」，醫生生氣的跺了一腳，轉身離開。

此時進來了一位高大的軍人「我們找不到團長費格萊茵，他不再工事中」「甚麼？找不到費格萊茵？那就繼續找啊，我要立刻見到費格萊茵，如果他沒有命令就這樣跑掉，那他就是逃兵，是叛徒，叫費格萊茵來」元首的怒氣值max「費格萊茵！費格萊茵！費格萊茵！」

醫生回到了他的住處，穿好他的軍裝坐在餐桌前「爸爸，你為什麼今天要穿周末才穿的制服？」醫生笑而不語「昂斯特，出了什麼是嗎？」醫生老婆擔心的問「沒有」。餐桌下，醫生默默地轉開了兩顆手榴彈，將他們的引線交錯，拔掉...碰的一聲爆炸，醫生女兒的洋娃娃被炸飛到屋外。

此時黨衛軍進入了柏林最複雜的舞廳中，有很多間房間通過地道連樣舞廳，一些房間之中也有地道連結，這裡的男人女人們赤裸著身體跳著舞，一旁的人醉的不省人事。這裡的地道很特別，每間房間連到其他房間的通道各有不同的柵門，且其柵門有特別的設計，有些只能由內向外開，有些則只能由外向內開。每條地道都有不同的長度，黨衛軍首領只知道這裡包括舞廳總共有$N$間房間，費格萊茵就藏身在其中一間，為了找到費格萊茵，他派了$N-1$個士兵，由地道分別前往其他$N-1$間房間進行搜查，終於在其中一間房間找到剛和妻子交配完的費格萊茵。

「團長你被捕了」「什麼？」「你有當逃兵的嫌疑，穿上衣服跟我們走」「去你的」士兵們看到費格萊茵不鳥他們，於是上前直接逮捕他「放開我！你有甚麼資格命令我」，在收到費格萊茵被捕的消息後，嫂夫人在元首面前下跪求情「你不會處決赫爾曼的，是嗎？」「證據確鑿，他想逃跑」「那有怎樣？一切都結束了，想想我可憐的妹妹，她已經懷了赫爾曼的孩子」「他是希姆萊的同夥，他也是叛國者；對叛國者不能仁慈，不能同情他們」元首伸手摸摸愛娃的臉「他將被送上軍事法庭然後處死」「可是現在這又甚麼用」「這是我的願望！」元首氣憤地大吼，愛娃擦了擦眼淚「你是元首」。

黨衛軍的士兵們從舞廳尋找費格萊茵躲藏的房間時，因為已經事先調查過地道的結構，所以每位士兵可以用最短的距離到達目標房間。在搜查完之後士兵會從目標房間走回舞廳，當然也是最短的路線，現在黨衛軍首領想知道他的士兵們加起來總共走了多長的距離，請你告訴他吧！

InputFile

第一行輸入兩個正整數$N(1\leq N \leq 10^6)$及$M(1\leq M \leq 10^6)$以空白區分，其中$N$表示房間總數$M$表示房間之間的通道總數。

接下來的$M$行，每一行輸入三個正整數$P,Q,R$，表示從房間$P$可進入一個單向通道到房間$Q$，且經過該通道需的長度為$R$。所有通道的長度總和將小於$1000000000$。

各房間分別以一個$1$到$N$的正整數表示，且舞廳固定設在編號$1$的房間。

OutputFile

請輸出一個整數，表示長官想知道的答案並換行，如果有從舞廳無法走到的房間或是有房間無法走回舞廳請輸出0

範例輸入

範例輸出

限制:

時限	100ms
記憶體	65535000 bytes

Judge Setting

run-time limit: 150 ms
memory limit: 65535000 byte
測資數量: 0