/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
晴れて天使学校を卒業したタプリスたち、天使 1 から天使 N までの N 人の天使たちが下界に降りてきました！ そして、先輩である天真さんを見習って引きこもることにしました！
しかし、このままではお互いに会えなくなってしまうことに気が付いた天使たちは、お互いの住んでいる部屋に行けるように、バス路線のうち長さ L 以下の路線に無料で乗ることができる、無料チケットを手に入れることにしました。
下界のバスは M 路線あり、i 番目の路線は天使 A_i が引きこもっている部屋と天使 B_i が引きこもっている部屋を双方向に結んでおり、路線の長さは C_i です。
天使たちは寂しがり屋なので、それぞれの天使が q 人以上の天使に会えない場合、寂しさから堕天してしまいます。
そこで、タプリスは天使たちがどの程度の寂しがり屋でも対応できるように、いくつかのqについて、購入する必要のあるバスの無料券の路線の上限の長さ、L の最小値を求めようと思いましたが、難しかったのであなたに頼むことにしました。
あなたの仕事は、Q回のクエリで、それぞれ与えられる q_i について 、全ての天使が自分を含めて q_i 人以上の天使に会えるために必要なL (L \geq 0)を求めることです。
なお、天使は無料チケット以外で移動することはできないものとします。
制約
- 入力は全て整数である
- 2 \leq N, M, Q \leq 10^5
- 1 \leq A_i, B_i \leq N
- 0 \leq C_i \leq 10^{10}
- 1 \leq q_i \leq 10^5
- 与えられるグラフは単純とも連結とも限らない
入力
入力は以下の形式で標準入力から与えられます。
N M Q
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_{M-1} B_{M-1} C_{M-1}
A_M B_M C_M
q_1
q_2
⋮
q_{Q-1}
q_Q
出力
Q 行に渡って出力してください。
i 行目には、i 個目のクエリに対する最小の L の値を出力してください。
なお、どのような L の値を設定しても条件が達成できない場合は、このクエリの答えとして trumpet と出力してください。
入力例1
9 10 4
1 2 3
1 4 1
3 4 4
2 3 1
4 5 9
5 6 3
6 7 4
7 8 2
8 9 3
6 9 5
2
3
5
10
出力例1
3
4
9
trumpet
例えば、1 個目の質問に対して、全ての天使は自分を含めて 2 人以上と会えなければなりません。
この例において、L = 2 の場合と L = 3 の場合の無料チケットが使えるバスは以下の図のようになります。
この図において、L = 2 の場合、天使 5, 6, 9 は自分を含め 1 人の天使にしか会うことはできません。
L = 3 になると、天使 1 は天使 {1, 2, 3, 4} と、天使 5 は天使 {5, 6} と、天使 7 は天使 {7, 8, 9} と会うことができます。このように、全ての天使は自分を含め 2 人以上の天使に会うことができます。
よって、q_1 = 2 の場合の答えは 3 です。
writer: Thistle