问题描述

Marvolo站在机房窗前，望着外面当空飞舞的落叶，一时陷入了沉思。

“Marvolo？”Sherc叫道，”你怎么了？”

“今天是光棍节，他在哪里感伤什么？难不成……”Mike和Sherc对视一眼，不约而同地露出恍然大悟的神色。

“不，我只是在想，前年的今天，好像是NOIP来着，好怀念当时的日子……” “……”

Marvolo是一个有情怀的人。他经常去散步，在散步中放松自己，思考人生。最近秋意渐起，落叶多了起来。在这个季节里，Marvolo很喜欢找一条无人的小路，伴随着纷纷扬扬的落叶散步。作为一个理科生，他对于散步这个过程也十分严谨。他把机房附近的道路转化为了一个无向图。机房编号为1，Marvolo的家编号为N。有M条道路连接着这N个点，经过每条路都需要花费一个时间Li。落叶的景观最多还能够持续K天，所以在这K天中Marvolo在每天都要找到一条从机房回家的路。但是最近城里施工，会有一些点无法通行，可能会让他被迫更改路线。这让Marvolo很是苦恼。尽管Marvolo喜欢散步，但是他不想浪费太多的时间在路上。他通常会有一条固定的回家路线，但是每次更改路线时，他都要花费P时间重新想一条路线回家。他希望你可以帮他找到一个回家的方案，使得他在K天内花费的时间最少。

【输入格式】

第一行有四个整数K,N,P,M含义如上文描述。

接下来M行，每行有三个数X,Y,L。表示从X到Y有一条长度为L的路径。

接下来一行，一个整数S。

接下来S行，一行有三个整数C,A,B。表示C节点在[A,B]这个时间内不可通过。

【输出格式】

一个整数，表示总花费时间的最小值。

【样例输入】

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

【样例输出】

32

前三天走1-4-5，后两天走1-3-5，这样总时间为(2+2)*3+(3+2)*2+10=32

【数据范围】

对于100%的数据，1<=K<=100,1<=N<=20。保证答案在Longint(Int)范围内。保证每天存在从1到N的路线。