E : Arojam's Mask / 仮面

問題文

あなたは勇者である。勇者が旅をしている世界は N 個の街と、異なる街同士を結ぶ M 本の道からなる。道 i は街 a_i と街 b_i を結び、双方向に移動可能である。

街 S から出発し、街 T に移動することが勇者の目的である。 S,T は異なる街である。勇者は 0 日目に街を出発し、ちょうど 1 日かけて 1 本の道を通って移動することができる。道を使った移動には日数の制限 R があり、R 日目を超えることはできない。

また、勇者は任意の街で「オカリナを吹く」こともできる。オカリナを吹くと、時は 0 日目に、位置は街 S に戻される。つまり、R 回を超える移動を行う場合は、最低一度はオカリナを吹かなければならない。

さらに、勇者がある街に位置すると「イベント」が発生することがある。イベントは E 種類あり、i 番目のイベントは、街 c_{i} で発生する。イベントは勇者がそこにいると自動的に発生し、新たに道 a’_i と b’_i を結ぶ道が生じる。この道はオカリナを吹いても消えることはなく、初めから存在する道とも、別のイベントによって追加される道とも重複しない。ある町で起こるイベントは高々1つである。

さて、勇者の今日の仕事は、街 T に到達するまでに必要な移動の回数とオカリナを吹く回数の和の最小値を求めるプログラムを書くことである。

入力

入力は以下の形式で与えられる。

N M E S T R
a_{0} b_{0}
…
a_{M−1} b_{M−1}
a’_{0} b’_{0} c_{0}
…
a’_{E−1} b’_{E−1} c_{E−1}

制約

入力はすべて整数である
2 \≤ N \≤ 100
1 \≤ M+E \≤ N(N−1)/2
0 \≤ E \≤ 4
0 \≤ R \≤ 100
0 \≤ S,T,a_i,b_i,a’_i,b’_i,c_i \≤ N−1
S ≠ T
a_{i} ≠ b_{i}, a’_{i} ≠ b’_{i}
a_{i} と b_{i}、a’_{i} と b’_{i}の全ての組は重複しない
i ≠ j なら c_{i} ≠ c_{j}

出力

答えを一行で出力せよ。どうしても T へ到達できない場合は −1 を出力せよ。

サンプル

サンプル入力1

8 5 2 0 5 5
0 1
0 3
0 6
1 2
6 7
3 4 7
4 5 2

サンプル出力1

例えば以下のように移動すればよい。イベントを起こすまでは道(4,5), (3,4)は存在しないことに注意せよ。

街2に行くと4から5へ移動できるようになる
オカリナを使用し0へ戻る
街7に行くと3から4へ移動できるようになる
オカリナを使用し0へ戻る
0から5へまっすぐ進む

サンプル入力2

7 5 1 0 6 8
0 1
1 2
2 3
3 4
4 5
3 6 5

サンプル出力2

オカリナを1度も吹かない経路が最適である。

サンプル入力3

4 1 4 1 2 3
3 1
3 2 0
0 1 3
0 3 1
0 2 2

サンプル出力3

街 S でイベントが起こることもある。