import java.util.*

fun main(args:Array<String>?): Unit {
    val (n, m, e, s, t, r) = readLine()!!.trim().split(' ').map(String::toInt)
    val nodes = Array(n){Stack<Int>()}
    repeat(m){
        val (a, b) = readLine()!!.trim().split(' ').map(String::toInt)
        nodes[a].push(b)
        nodes[b].push(a)
    }
    val events = Array(e){
        val (a, b, c) = readLine()!!.trim().split(' ').map(String::toInt)
        Event(a, b, c)
    }
    val minStep = Array(1 shl e){Array(r + 1){BooleanArray(n){false}}}
    val queue: Queue<Pair<State, Int>> = LinkedList<Pair<State, Int>>()
    val start = State(s, (0 until e).find{events[it].c == s})
    queue.add(Pair(start, 0))
    minStep[start] = true
    while(queue.isNotEmpty() && queue.peek().first.position != t){
        val (state, step) = queue.poll()
        if (state.day != r) {
            for (to in nodes[state.position]) {
                val next = (0 until e).find{events[it].c == to}?.let{state.moveWithEvent(to, it)} ?: state.move(to)
                if (!minStep[next]){
                    minStep[next] = true
                    queue.add(Pair(next, step + 1))
                }
            }
            for (i in events.indices) if (state.isEventHappened(i) && (events[i].a == state.position || events[i].b == state.position)) {
                val to = if (events[i].a == state.position) events[i].b else events[i].a
                val next = (0 until e).find{events[it].c == to}?.let{state.moveWithEvent(to, it)} ?: state.move(to)
                if (!minStep[next]){
                    minStep[next] = true
                    queue.add(Pair(next, step + 1))
                }
            }
        }
        val next = state.ocarina(s)
        if (!minStep[next]){
            minStep[next] = true
            queue.add(Pair(next, step + 1))
        }
    }
    println(if (queue.isEmpty()) -1 else queue.peek().second)
}
operator fun Array<Array<BooleanArray>>.get(state: State): Boolean = this[state.events][state.day][state.position]
operator fun Array<Array<BooleanArray>>.set(state: State, value: Boolean): Unit {
    this[state.events][state.day][state.position] = value
}
operator fun List<Int>.component6(): Int = this[5]
data class Event(val a: Int, val b: Int, val c: Int)
class State private constructor(val events: Int, val day: Int, val position: Int) {
    fun move(destination: Int): State = State(events, day + 1, destination)
    fun moveWithEvent(destination: Int, event: Int): State = State(events or (1 shl event), day + 1, destination)
    fun ocarina(start: Int): State = State(events, 0, start)
    fun isEventHappened(event: Int): Boolean = (events and (1 shl event)) != 0
    constructor(start: Int):this(start, null)
    constructor(start: Int, event: Int?): this(event?.let{1 shl it} ?: 0, 0, start)
}
