TopCoder

Thumb 100
西瓜
いつか、私を助けてね

User's AC Ratio

92.5% (37/40)

Submission's AC Ratio

21.8% (70/321)

Description

在一個神祕的城堡中,其地底建造了許多地道及房間。每間房間連到其他房間的通道各有不同的柵門,且其柵門有特別的設計,有些只能由內向外開,有些則只能由外向內開。國王把這些房間用來當作囚房,除了一間房間做為侍衛休息室以外,其他每間房間皆做為一個囚犯的囚房。這些囚犯每天白天負責工作,到了晚上每位囚犯有專屬的侍衛,將他們一一帶到囚房。

由於要防止囚犯脫逃,除了侍衛休息室以外,地道及房間中皆沒有燈光。因此每天每位侍衛必須分配一個油燈,從侍衛休息室將囚犯帶到他們的房間,再回到侍衛休息室,在這段時間內皆必須點亮油燈。國王是個很節儉的人,為了節省侍衛油燈所消耗的油,他派人根據房間之間的地道長度所需行走時間,量測出經過每段通道使用油燈的耗油量。國王精打細算的要求這些侍衛每天使用油燈的耗油總量必須為最低。但由於侍衛將囚犯帶到房間的時間可能不同,因此不必考慮侍衛共用油燈的可能。

請以一個程式,根據所給房間通道及經過房間通道所需的耗油量,找出侍衛每天使用油燈的最低耗油總量。

Input Format

第一行輸入兩個正整數 M 及 N 以空白區分,1<=M<=1000000,1<=N<=1000000,其中 M 表示房間總數,N 表示房間之間的通道總數。

接下來的 N 行,每一行輸入三個正整數 P、Q、及 R,表示從房間 P 可進入一個通道到房間 Q,且經過該通道需要消耗 R單位的油。所有通道的耗油量總和將小於 1000000000。

各房間分別以一個 1 到 M 的正整數表示,且侍衛休息室固定設在編號 1 的房間。

Output Format

輸出侍衛每天使用油燈的最低耗油總量。若所給通道資料無法由侍衛休息室通到某一間房間,請輸出0。

Sample Input

Sample Input #1

2 2
1 2 10
2 1 25

Sample Input #2

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

Sample Output #1

35

Sample Output #2

210

Hints

Problem Source

原TIOJ1509 / TOI2008初選(prob 4)

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536
4 3000 65536 65536