0771 - KKK係数

問題

わたしは、W国にすんでいる。この国は、N+1個の都市と、その都市間を結ぶL本の道で構成されている。　また、W国は国民全員がコーヒーを愛していて、国民全員が常にコーヒーを携帯しているほどだ。

そんなこの国では、ある不思議な現象がおきる。それはコーヒーを持ったまま道をあるくと、コーヒーがこぼれるのである。
そこで、W国の研究者がコーヒー会社別にコーヒーがこぼれる法則性を調査した結果、　それぞれの会社のコーヒーが　ある数K(会社によって異なる)　に比例してコーヒーがこぼれることがわかった。
研究者たちは、この 「K」 を　KKK係数(各社のコーヒーのこぼれ係数)とした。そして、コーヒーは 道の長さ C と　KKK係数K　の　積　でこぼれることがわかった。

わたしは、コーヒーの中でも DYD0会社　HC会社 CC会社 の三種類のコーヒーがすきなのである。

そこで、あなたの出番だ。わたしは、一番大きい都市番号N , 道の本数L , 道の情報A B C(AからBまでの距離はC), 3種類のKKK係数　X Y Z をあなたに教える。X、Y、Zはそれぞれ、

• X → DYD0会社のKKK係数
• Y → HC会社のKKK係数
• Z → CC会社のKKK係数

である。
わたしは、どの都市でコーヒーを買えば、その都市からほかの都市に行ったとき、一番コーヒーがこぼれないかを知りたい。
なので、あなたには、コーヒーを買う都市 I(いく都市の始点となる都市) と どのくらいコーヒーがこぼれるか P と　どの会社のコーヒーかコーヒー会社の名前　を出力してほしい。
どのくらいコーヒーがこぼれるかP　は、始点となる都市I から、それぞれの都市に行ったときのコーヒーがこぼれた量の総和であり、都市をまわるわけではない。

例えば、図のような都市構成だったならば、
都市０を始点Iとしたとき、それぞれの都市への最短ルートは、
0 → 1 = 10
0 → 2 = 15
0 → 3 = 14
であり、コーヒーがこぼれる量は、 (10+15+14)にKKK係数をかけた数値である。
ちなみにこの例では、都市1を始点とするのがもっともよい解である。
こぼれる総量が同じ会社があった場合は、空白区切りでDYD0 HC CC　の順で出力せよ。

注意点

• 入力で与えられる都市は、二度と同じ組み合わせは与えられない。
  (例として、　1 2 10　と与えられた後にはそれ以降の入力で、 1 2 10　や 2 1 10は与えられない)
• どの都市を始点にしてもすべての都市にいけることにする。
• 都市間は、A→B にも、 B→A　にもいくことができ、それぞれＣの距離がかかる。
• 都市は何度でも通ってもよいこととする。
• コーヒー会社でこぼれるコーヒーが同じ量だった場合、空白区切りで、DYD0 HC CCの順で出力せよ。
• また、こぼれるコーヒーの量が最小となる都市のいきかたの始点となる都市が複数ある場合には、数字が小さい都市を出力すること。
• 最初の都市には戻ってこなくてよいし、元の都市に戻る距離はないものとする。
• 例のように、Nは都市番号であり、実際には0~N個の都市があることに注意せよ。

入力

N L
A0 B0 C0 
...
AL-1 BL-1 CL-1 
X Y Z

1 行目に整数 N L K が都市番号、道の本数、KK係数の順で与えられる。

2 行目から2+L行目まで整数 A B C が都市Aと都市Bの距離Cが与えられる。

2+L+1行目には整数 X Y Z がそれぞれ DYD0会社 HC会社 CC会社の順でKKK係数が与えられる。

出力

I P [NAME] 

コーヒーを買う都市 I(回る都市の始点となる都市) と
どのくらいコーヒーがこぼれるかP と買うコーヒー会社の名前[NAME]を出力せよ。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ N ≦ 300
• N ≦ L ≦ 44849
• 0 ≦ A,B ≦ N
• 0 ≦　C ≦ 100
• 1 ≦ X,Y,Z ≦ 100

与えられる数字はすべて整数である。

---

入出力例

入力例1

4 6
0 1 80
1 2 20
0 2 60
2 3 50
3 4 60
1 4 90
1 2 3

出力例1

2 240 DYD0

入力例2

2 2
0 1 1
1 2 1
10 0 9

出力例2

1 0 HC

入力例3

4 6
0 1 80
1 2 20
0 2 60
2 3 50
3 4 60
1 4 90
1 2 1

出力例3

2 240 DYD0 CC

余談

DYD0の0は半角0(数字の0)であって、oでもOでもありません。間違えないようにしてください。
問題文に出てくる雑絵はei1612が描いたものです。わかりづらかったらすみません。