#include <bits/stdc++.h>
using namespace std;

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

constexpr int dx[] = {0, -1, 1, 0, -1, 1, -1, 1};
constexpr int dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    int n, m, e, s, t, r;
    cin >> n >> m >> e >> s >> t >> r;

    auto G = make_vector(n, 0, 0);
    range(i, 0, m) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector< int > as(e), bs(e), cs(e);
    range(i, 0, e) {
        cin >> as[i] >> bs[i] >> cs[i];
    }

    struct type {
        int dist, cnt, bit, day, v;
        type(int dist, int cnt, int bit, int day, int v) : dist(dist), cnt(cnt), bit(bit), day(day), v(v) {}
    };

    auto cmp = [](const type a, const type b) {
        return a.dist > b.dist;
    };

    priority_queue< type, vector< type >, decltype(cmp) > pq{cmp};
    int sbit = 0;
    range(i, 0, e) {
        if (cs[i] == s) sbit = sbit | (1 << i);
    }
    pq.emplace(0, 0, sbit, 0, s);
    auto d = make_vector(5, 1 << e, r + 1, n, inf);
    d[0][sbit][0][s] = 0;

    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();

        int cnt = p.cnt;
        int bit = p.bit;
        int day = p.day;
        int v = p.v;

        if (p.dist > d[cnt][bit][day][v]) continue;

        if (cnt < 4 && chmin(d[cnt + 1][bit][0][s], d[cnt][bit][day][v] + 1)) {
            pq.emplace(d[cnt + 1][bit][0][s], cnt + 1, bit, 0, s);
        }

        if (day == r) continue;
            
        for (auto u: G[v]) {
            int nbit = bit;
            range(i, 0, e) {
                if (u == cs[i]) nbit = nbit | (1 << i);
            }

            if (chmin(d[cnt][nbit][day + 1][u], d[cnt][bit][day][v] + 1)) {
                pq.emplace(p.dist + 1, cnt, nbit, day + 1, u);
            }
        }

        range(i, 0, e) {
            if ((bit & (1 << i)) == 0) continue;
            if (as[i] == v) {
                int nbit = bit;
                range(j, 0, e) {
                    if (bs[i] == cs[j]) nbit = nbit | (1 << j);
                }
                if (chmin(d[cnt][nbit][day + 1][bs[i]], p.dist + 1)) {
                    pq.emplace(p.dist + 1, cnt, nbit, day + 1, bs[i]);
                }
            }
            if (bs[i] == v) {
                int nbit = bit;
                range(j, 0, e) {
                    if (as[i] == cs[j]) nbit = nbit | (1 << j);
                }
                if (chmin(d[cnt][nbit][day + 1][as[i]], p.dist + 1)) {
                    pq.emplace(p.dist + 1, cnt, nbit, day + 1, as[i]);
                }
            }
        }

    }

    int ans = inf;
    range(cnt, 0, 5) range(bit, 0, (1 << e)) range(day, 0, r + 1) {
        chmin(ans, d[cnt][bit][day][t]);
    }

    if (ans == inf) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

signed main(int argc, char *argv[]) {
    solver();
}



Measured memory_bytes: 5888