1027 - Takenoko Christmas Tree

時間制限 1 秒 / メモリ制限 64 MB / 得点 2 / Writer ei1821 / x 6 / 統計 /

TLE
1sec
MLE
64MB
得点
2
writerに問題があったのでRejudgeしました 20181222 19:20

ストーリー

ei1821は筍派(急進派)である。

12月25日はクリスマスである。
よく街中では針葉樹をデコレートしてクリスマスを彩るが、ここMeiji-Cityではクリスマスツリーに代わり筍がツリー扱いを受けている。
理由としては、古来よりMeiji-Cityにて筍が別名「知恵の実」と呼ばれ、神聖視されているからだと言われている（市長の趣味とも言われている)。
閑話休題。
Meiji-City各所には巨大な筍がおかれ、飾りつけがされている。
周囲を照らすために電球も設置されているのだが、電工士は頭がおかしいのか筍に装飾を施したときにN個の電球を結ぶ電線を必要以上につなげあうという愚行をした。
複数箇所から電力供給があったときの電流電圧がどうなるかはわからない（考えたくない）が、一つ確かなことがあるはずだ。

お 金 が 無 駄 に な る

電球Aと電球B間には分間X円の料金がかかり、電球Bと電球Cには分間Y円の料金がかかる。もし、XとYに大小関係があるならば安く照らせる方だけのこしてしまい、後は全て断線してやろうと考えた。
この電工士はさらに信用ならず、全ての電球が光るように電線を繋げていない。
一つ5000兆円かかる電球を買ったのに使わないのはもったいないので、電流の流れないような配線がされた電球たちをつなげるためには分間C円かかる汎用電線一本を適当につなげることでどうにかする。
汎用電線は注文に時間がかかるので汎用電線の使用本数は最低限にすませたい。
電源供給の大元は筍の下のコンセント一つのみであり、電流の流れる向きは電球AiとBiどちらから流れてもかまわない。
電球全てを照らすとき、最低でも分間いくらお金がかかるだろうか。

入力

1行目に、電球の数N、電球同士をつなぐ電線の本数Mが与えられる。
2行目以降M行に渡って、電気がどこからどこに分間何円で流れるかを表す値 Ai Bi Xiが与えられる。
M+1行目に、汎用電線の値段Cが与えられる。
N  M
A1  B1  X1
A2  B2  X2
...
AM  BM  XM
C

出力

電球全てを照らすときの一分間で消費される金額を一行で出力せよ。
最後の改行を忘れずに。

制約

  • 1 ≤ $N$ ≤ 100,000
  • 1 ≤ $M$ ≤ 500,000
  • 0 ≤ $C$ ≤ 114,514
  • 0 ≤ $A$i ≤ N
  • 0 ≤ $B$i ≤ N
  • $A$i ≠ $B$i
  • 1 ≤ $X$i ≤ 1000
  • Aiの値のうちコンセントを0とし、1以降を電球とする

入出力例

例1

入力

5 8
0 1 10
0 3 5
1 2 1
1 3 1000
1 4 500
2 3 100
2 4 10000
3 4 5000
5

出力

521
コンセントから電球4までつながっており、
コンセント(=0)から電球1間に10円、1から2に1円、コンセントから3に5円、1から4に500円で、分間516円かかる。
電球5は繋がっていないので、電球5とどこかを5円で適当につなげることで点灯させる。
よって、分間521円かかることになる。

例2

入力

8 8
0 1 100
1 2 200
2 3 300
3 4 400
4 5 500
5 6 600
6 7 700
7 8 800
1

出力

3600
汎用電線を8つ用意すれば8円で確実に安くなるが、出来るだけ使わないようにしているので汎用電線0本で分間3600円かかる。

例3

入力

150 0
10000

出力

1500000
本当にこの電工士は仕事をしたのだろうか。

例4

入力

2 1
1 0 10
1000

出力

1010
更新前のコーナーケース

補足


筍を照らす電球のフィラメントはもちろん竹。
LEDなんて使わない。
なお、このなんたらはフィクションであり、実際の地名とは関係なく、物理法則も異なっているので電流が閉路でなくても流れます。
どんな謎理論が展開されていてもフィクションなので仕方がありません。