#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
struct road
{
	int a, b, d;
};
struct crime
{
	int x, t, w;
};
struct policeman
{
	vector<int> xs;
	vector<int> ts;
};
struct task
{
	int N, E, P, C;
	vector<road> roads;
	vector<crime> crimes;
	vector<policeman> policemen;

	void read(ifstream& fin)
	{
		fin >> N >> E >> P >> C;

		roads.resize(E);
		for (auto& r : roads)
			fin >> r.a >> r.b >> r.d;

		crimes.resize(C);
		for (auto& c : crimes)
			fin >> c.x >> c.t >> c.w;
	}

	void solve()
	{
		sort(crimes.begin(), crimes.end(), [](const crime& l, const crime& r) {return l.t < r.t || l.t == r.t && r.w > l.w; });

		policemen.resize(P);
		for (int p = 0, c = 0; p < P && c < C; c++)
		{
			auto& crime = crimes[c];
			for (int w = 0; p < P && w < crime.w; w++, p++)
				policemen[p].xs.push_back(crime.x);
		}
	}

	void write(ofstream& fout)
	{
		for (auto& p : policemen)
		{
			int c = p.xs.size();
			fout << c << endl;
			if (c > 0)
			{
				for (int i = 0; i < c; i++)
					fout << p.xs[i] << ' ';
				fout << endl;
				for (int i = 0; i < p.ts.size(); i++)
					fout << p.ts[i] << ' ';
				fout << endl;
			}
		}
	}
};
int main()
{
	ifstream fin("minority_report.in");
	task t;
	t.read(fin);

	t.solve();

	ofstream fout("minority_report.out");
	t.write(fout);
}