Time Limits: 1000 ms Memory Limits: 262144 KB

Description

BOSS送给小唐一辆车。小唐开着这辆车从PKU出发去ZJU上课了。

众所周知，天朝公路的收费站超多的。经过观察地图，小唐发现从PKU出发到ZJU的所有路径只会有N（2<=N<=300）个不同的中转点，其中有M（max(0, N-100) <=M<=N）个点是天朝的收费站。N个中转点标号为1…N，其中1代表PKU，N代表ZJU。中转点之间总共有E（E<=50,000）条双向边连接。

每个点还有一个附加属性，用0/1标记，0代表普通中转点，1代表收费站。当然，天朝的地图上面是不会直接告诉你第i个点是普通中转点还是收费站的。地图上有P（1<=P<=3,000）个提示，用[u, v, t]表示：[u, v]区间的所有中转点中，至少有t个收费站。数据保证由所有提示得到的每个点的属性是唯一的。

车既然是BOSS送的，自然非比寻常了。车子使用了世界上最先进的DaxiaYayamao引擎，简称DY引擎。DY引擎可以让车子从U瞬间转移到V，只要U和V的距离不超过L（1<=L<=1,000,000），并且U和V之间不能有收费站（小唐良民一枚，所以要是经过收费站就会停下来交完钱再走）。

DY引擎果然是好东西，但是可惜引擎最多只能用K（0<=K<=30）次。

Input

第一行有6个整数N，M，E，P，L，K分别代表：N个中转点，M个收费站，E条边，P个提示，DY引擎的有效距离L，DY引擎的使用次数K。

接下去E行，每行有3个整数u，v，w（1<=u, v<=N; 1<=w<=1,000,000）表示：u和v之间有一条长度为w的双向边。

接下去P行，每行有3个整数u，v，t（1<=u<=v<=N； 0<=t<=u-v+1）表示： [u, v] 标号区间至少有t个收费站。

Output

输出一个整数，表示小唐从PZU开到ZJU用的最短距离（瞬间转移距离当然是按0来计算的）。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6 2 6 2 5 1

1 2 1

2 3 2

3 6 3

1 4 1

4 5 2

5 6 3

2 5 2

4 6 2

Sample Output

1
2
3
4
5
1

【样例解释】

    4、5是收费站。1->2(1)->6(1)

Data Constraint

对于30%的数据保证：

2<=N<=30，max(0, N-10) <=M<=N，0<=k<=10

对于100%的数据保证：

2<=N<=300，max(0, N-100) <=M<=N，E<=50,000，1<=P<=3,000，1<=L<=1,000,000，0<=K<=30

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 302
#define M 50002
#define K 32

int n, m, e, p, l, t, tot, ans = inf;
int to[(M << 1) * K], len[(M << 1) * K], nxt[(M << 1) * K], head[N * K];
int edge[M][3], f[N][N], dis[N * K], vis[N * K];

void add(int u, int v, int w) {
    to[++tot] = v; len[tot] = w;
    nxt[tot] = head[u]; head[u] = tot;
}

void spfa(int x, int y) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    queue<int> q;
    dis[x] = y; q.push(x);
    while (!q.empty()) {
        int now = q.front(); q.pop(); vis[now] = 0;
        for (int i = head[now]; i; i = nxt[i])
            if (dis[to[i]] > dis[now] + len[i]) {
                dis[to[i]] = dis[now] + len[i];
                if (!vis[to[i]]) {
                    vis[to[i]] = 1; q.push(to[i]);
                }
            }
    }
}

void floyd() {
    for (int k = 1; k <= n; k++)
        if (!(dis[k] - dis[k - 1]))
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (i != j && i != k && j != k)
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &e, &p, &l, &t);
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= e; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge[i][0] = u; edge[i][1] = v; edge[i][2] = w;
        f[u][v] = f[v][u] = min(f[u][v], w);
    }
    for (int i = 1; i <= p; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(v, u - 1, -w);
    }
    for (int i = 2; i <= n; i++)
        add(i, i - 1, 0), add(i - 1, i, 1);
    spfa(n, m); floyd();
    memset(head, 0, sizeof head); tot = 0;
    for (int i = 1; i <= e; i++)
        for (int k = 0; k <= t; k++) {
            add(k * n + edge[i][0], k * n + edge[i][1], edge[i][2]);
            add(k * n + edge[i][1], k * n + edge[i][0], edge[i][2]);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && f[i][j] <= l)
                for (int k = 0; k < t; k++)
                    add(k * n + i, (k + 1) * n + j, 0);
    spfa(1, 0);
    for (int k = 0; k <= t; k++)
        ans = min(ans, dis[k * n + n]);
    printf("%d\n", ans);
    return 0;
}