#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

const int INF = INT_MAX / 4;

void shortestPath(const vector<vector<int> >& edges, int start, vector<int>& dist)
{
    int n = edges.size();
    dist.assign(n, INF);
    dist[start] = 0;
    queue<int> q;
    q.push(start);

    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(unsigned i=0; i<edges[v].size(); ++i){
            int u = edges[v][i];
            if(dist[u] == INF){
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}

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

    vector<vector<int> > edges(n);
    for(int i=0; i<m; ++i){
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    vector<int> a(e), b(e), c(e);
    for(int i=0; i<e; ++i)
        cin >> a[i] >> b[i] >> c[i];
    c.push_back(s);
    c.push_back(t);

    vector<vector<vector<int> > > dist(1<<e, vector<vector<int> >(e+2, vector<int>(e+2)));
    for(int i=0; i<(1<<e); ++i){
        bitset<32> bs(i);
        for(int j=0; j<e; ++j){
            if(bs[j]){
                edges[a[j]].push_back(b[j]);
                edges[b[j]].push_back(a[j]);
            }
        }

        vector<int> dist2;
        for(int j=0; j<e+2; ++j){
            shortestPath(edges, c[j], dist2);
            for(int k=0; k<e+2; ++k)
                dist[i][j][k] = dist2[c[k]];
        }

        for(int j=0; j<e; ++j){
            if(bs[j]){
                edges[a[j]].pop_back();
                edges[b[j]].pop_back();
            }
        }
    }

    vector<vector<vector<int> > > dp(1<<e, vector<vector<int> >(r+1, vector<int>(e+2, INF)));
    multimap<int, tuple<int, int, int> > mm;
    dp[0][r][e] = 0;
    mm.insert(make_pair(0, make_tuple(0, r, e)));

    while(!mm.empty()){
        int cost = mm.begin()->first;
        int eve, oca, cur;
        tie(eve, oca, cur) = mm.begin()->second;
        mm.erase(mm.begin());
        if(cost > dp[eve][oca][cur])
            continue;

        if(cost + 1 < dp[eve][r][e]){
            dp[eve][r][e] = cost + 1;
            mm.insert(make_pair(cost + 1, make_tuple(eve, r, e)));
        }

        for(int i=0; i<e+2; ++i){
            int cost2 = cost + dist[eve][cur][i];
            int eve2 = eve;
            if(i < e)
                eve2 |= 1 << i;
            int oca2 = oca - dist[eve][cur][i];
            if(oca2 < 0)
                continue;
            if(cost2 < dp[eve2][oca2][i]){
                dp[eve2][oca2][i] = cost2;
                mm.insert(make_pair(cost2, make_tuple(eve2, oca2, i)));
            }
        }
    }

    int ans = INF;
    for(int i=0; i<(1<<e); ++i){
        for(int j=0; j<=r; ++j){
            ans = min(ans, dp[i][j][e+1]);
        }
    }
    if(ans < INF)
        cout << ans << endl;
    else
        cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 3324