#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

struct Edge
{
	int v, w;
	Edge(int v, int w)
	{
		this -> v = v;
		this -> w = w;
	}
};

int _n, _m, _k, _e;
int _dis[21];
bool _vis[21];
int _ev[450];
int _eu[450];
int _ew[450];
int _dp[101];
bool _forb[21];
bool _down[101][21];
int _cost[101][101];
vector <Edge> _adj[101];

inline void Reset(int l, int r)
{
	_dis[1] = 0;	
	for (int i = 2; i <= _m; i++) _dis[i] = 2147483646;
	for (int i = 1; i <= _m; i++) _adj[i].clear();
	for (int i = 1; i <= _e; i++)
	{
		_adj[_eu[i]].push_back(Edge(_ev[i], _ew[i]));
		_adj[_ev[i]].push_back(Edge(_eu[i], _ew[i]));
	}
	for (int i = 1; i <= _m; i++)
	{
		for (int j = l; j <= r; j++)
		{
			if (_down[j][i]) _forb[i] = true;
		}
	}
	for (int i = 1; i <= _m; i++) _vis[i] = false;
	for (int i = 1; i <= _m; i++) _forb[i] = false;
}

inline void ReCalc()
{
	priority_queue <int> _Q;
	while (!_Q.empty()) _Q.pop();
	_Q.push(1);
	while (!_Q.empty())
	{
		int cur = _Q.top();
		_Q.pop();
		if (_forb[cur]) continue;
		if (_vis[cur]) continue;
		_vis[cur] = 1;
		for (vector <Edge> :: iterator it = _adj[cur].begin(); it != _adj[cur].end(); it++)
		{
			if (_dis[(*it).v] > _dis[cur] + (*it).w)
			{
				_dis[(*it).v] = _dis[cur] + (*it).w;
				if (!_vis[(*it).v] && !_forb[(*it).v])_Q.push((*it).v);
			}
		}
	}
}

inline void AddDown(int p, int a, int b)
{
	for (int i = a; i <= b; i++) _down[i][p] = 1;
}

	
int main()
{
	cin >> _n >> _m >> _k >> _e;
	for (int i = 1; i <= _e; i++)
	{
		cin >> _eu[i] >> _ev[i] >> _ew[i];
	}
	int d, p, a, b;
	cin >> d;
	for (int i = 1; i <= d; i++)
	{
		cin >> p >> a >> b;
		AddDown(p, a, b);
	}
	for (int i = 1; i <= _n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			Reset(j, i);
			ReCalc();
			_cost[j][i] = _dis[_m];
		}
	}
	for (int i = 1; i <= _n; i++)
	{
		_dp[i] = _cost[1][i] * i;
		for (int j = 0; j < i; j++)
		{
			_dp[i] = min(_dp[i], _dp[j] + _cost[j + 1][i] * (i - j) + _k);
		}
	}
	cout << _dp[_n] << endl;
}

样例输出 20