問題文

Simple RPGは勇者が仲間を集めながら魔王を倒すシンプルなRPGです。

勇者は \(N\) 頂点 \(M\) 辺からなるマップを移動します。 \(i\) 番目の辺は頂点 \(a_i\) から頂点 \(b_i\) へ移動することができ、長さは \(c_i\) です。

スタート時には勇者は頂点 \(1\) にいて、魔王は頂点 \(N\) にいます。

勇者は頂点 \(1\) から辺をいくつか経由して魔王のいる頂点 \(N\) へ行き、魔王を倒すのがこのゲームのクリア条件です。

しかし、魔王を倒すためには勇者だけでなく仲間の存在も必要です。

仲間候補は \(K\) 人いて、 \(i\) 人目の仲間候補は頂点 \(v_i\) にいます。

勇者が仲間候補のいる頂点に着くと、その場で仲間候補は仲間となってくれます。

魔王を倒すためには全ての仲間候補を仲間にしてから魔王のいる頂点へ行かなければなりません。

このゲームを遊んでいるフィーは、次の \(2\) つの実績を狙っています。

・実績「短」 : 魔王を倒すまでの勇者の移動距離がある一定時間より短い

・実績「長」 : 魔王を倒すまでの勇者の移動距離がある一定時間より長い

勇者の移動距離は、勇者の通った辺の長さの総和です。

この \(2\) つの実績を取るために、フィーはまずは魔王を倒すまでの勇者の移動距離の最短と最長を求めたくなりました。

フィーは計算が苦手なので、フィーの代わりに移動距離の最短と最長を求めて下さい。

ただし、辺の途中で立ち止まったり引き返したり、頂点に立ち止まったり、マップの外に出たりすることは出来ません。

入力

1行目には \(N, M, K\) が空白区切りで与えられます。

2行目以降の \(M\) 行にはマップの辺が与えられます。

　\(i+1\) 行目 \((1≦i≦M)\) には \(a_i, b_i, c_i\) が空白区切りで与えられます。

\(M+2\) 行目以降の \(K\) 行には仲間のいる場所が与えられます。

　\(M+i+1\) 行目 \((1≦i≦K)\) には \(v_i\) が与えられます。

出力

\(1\) 行目には魔王を倒すまでの勇者の最短移動距離、 \(2\) 行目には魔王を倒すまでの勇者の最長移動距離を出力して下さい。

移動距離が \(2^{63}-1\) を超える場合は代わりにlongを出力して下さい。

制約

• \(1≦N≦50,000\)


• \(1≦M≦100,000\)


• \(1≦K≦20\)


• \(1≦a_i, b_i≦N\)


• \(1≦c_i<2^{63}\)


• \(1≦v_i≦N\)


• \(a_i≠b_i\)


• \(i≠j\) なら \((a_i, b_i)≠(a_j, b_j)\)


• マップのグラフは連結である

小課題

小課題 Small

• \(1≦N≦300\)

小課題 Large

• \(1≦N≦1,000\)


• \(1≦M≦1,200\)

小課題 Only

• \(K=1\)

小課題 Haganai

• \(1≦K≦10\)

小課題 DAG

• マップのグラフには閉路がない。

小課題 Euglena

• 追加の制約はない。