#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int LOG = 20;
const int INF = 1e9;

struct SparseTable
{
	VI t[LOG];
	VI lg;
	int n;
	void init(int _n)
	{
		n = _n;
		lg.resize(n + 1);
		FOR(i, 2, n + 1)
			lg[i] = lg[i / 2] + 1;
		FOR(j, 0, LOG)
			t[j].assign(n, INF);
	}
	void build(const VI& v)
	{
		FOR(i, 0, SZ(v))
			t[0][i] = v[i];
		FOR(j, 1, LOG)
		{
			int len = 1 << (j - 1);
			FOR(i, 0, n - (1 << j) + 1)
			{
				t[j][i] = min(t[j - 1][i], t[j - 1][i + len]);
			}
		}
	}
	int query(int l, int r)
	{
		int i = lg[r - l];
		return min(t[i][l], t[i][r - (1 << i)]);
	}
};

struct SuffixArray
{
	int n;
	VI s;
	VI sa, rnk;
	
	void init(const VI& _s)
	{
		n = SZ(_s);
		s = _s;
		sa = suffixArray();
		rnk.resize(n);
		FOR(i, 0, n)
			rnk[sa[i]] = i;
	}
	void countSort(VI& p, const VI& c)
	{
		VI cnt(n);
		FOR(i, 0, n)
			cnt[c[i]]++;
		VI pos(n);
		FOR(i, 1, n)
			pos[i] = pos[i - 1] + cnt[i - 1];
		VI p2(n);
		for (auto x : p)
		{
			int i = c[x];
			p2[pos[i]++] = x;
		}
		p = p2;
	}
	VI suffixArray()
	{
		s.PB(-INF);
		n++;
		VI p(n), c(n);
		iota(ALL(p), 0);
		sort(ALL(p), [&](int i, int j)
		{
			return s[i] < s[j];
		});
		int x = 0;
		c[p[0]] = 0;
		FOR(i, 1, n)
		{
			if (s[p[i]] != s[p[i - 1]])
				x++;
			c[p[i]] = x;
		}
		int k = 0;
		while ((1 << k) < n)
		{
			FOR(i, 0, n)
				p[i] = (p[i] - (1 << k) + n) % n;
			countSort(p, c);
			VI c2(n);
			PII pr = {c[p[0]], c[(p[0] + (1 << k)) % n]};
			FOR(i, 1, n)
			{
				PII nx = {c[p[i]], c[(p[i] + (1 << k)) % n]};
				c2[p[i]] = c2[p[i - 1]];
				if (pr != nx)
					c2[p[i]]++;
				pr = nx;
			}
			c = c2;
			k++;
		}
		p.erase(p.begin());
		s.pop_back();
		n--;
		return p;
	}
};

struct Lcp
{
	VI lcp;
	SuffixArray a;
	SparseTable st;
	
	void init(const SuffixArray& _a)
	{
		a = _a;
		lcp = lcpArray();
		st.init(SZ(lcp));
		st.build(lcp);
	}
	VI lcpArray()
	{
		lcp.resize(a.n - 1);
		int h = 0;
		FOR(i, 0, a.n)
		{
			if (h > 0)
				h--;
			if (a.rnk[i] == 0)
				continue;
			int j = a.sa[a.rnk[i] - 1];
			for (; j + h < a.n && i + h < a.n; h++)
			{
				if (a.s[j + h] != a.s[i + h])
					break;
			}
			lcp[a.rnk[i] - 1] = h;
		}
		return lcp;
	}
	int queryLcp(int i, int j)
	{
		if (i == a.n || j == a.n)
			return 0;
		if (i == j)
			return a.n - i;
		i = a.rnk[i];
		j = a.rnk[j];
		if (i > j)
			swap(i, j);
		return st.query(i, j);
	}
};

VI a;
SuffixArray sa;
Lcp lcp;

struct Edge
{
	int u, v, l, p;
};

vector<Edge> edges;

bool cmp(const VI& path1, const VI& path2)
{
	if (path1.empty())
		return false;
	if (path2.empty())
		return true;
	int i[2] = {0, 0};
	int j[2] = {0, 0};
	while (i[0] < SZ(path1) && i[1] < SZ(path2))
	{
		const Edge& edge1 = edges[path1[i[0]]];
		const Edge& edge2 = edges[path2[i[1]]];
		int x = lcp.queryLcp(edge1.l + j[0], edge2.l + j[1]);
		int y[2] = {edge1.p - j[0], edge2.p - j[1]};
		if (x < y[0] && x < y[1])
		{
			return a[edge1.l + j[0] + x] < a[edge2.l + j[1] + x];
		}
		x = min(x, min(y[0], y[1]));
		FOR(t, 0, 2)
		{
			if (x == y[t])
			{
				i[t]++;
				j[t] = 0;
			}
			else
			{
				j[t] += x;
			}
		}
	}
	return i[0] == SZ(path1) && i[1] < SZ(path2);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, d, s;
	cin >> n >> m >> d >> s;
	s--;
	string str;
	cin >> str;
	edges.resize(m);
	vector<VI> g(n);
	FOR(i, 0, m)
	{
		Edge& edge = edges[i];
		cin >> edge.u >> edge.v >> edge.l >> edge.p;
		edge.u--;
		edge.v--;
		edge.l--;
		g[edge.u].PB(i);
	}
	a.resize(d);
	FOR(i, 0, d)
	{
		a[i] = str[i] - 'a';
	}
	sa.init(a);
	lcp.init(sa);
	VI used(n);
	vector<VI> bestPath(n);
	FOR(k, 0, n)
	{
		int v = k == 0 ? s : -1;
		if (k > 0)
		{
			FOR(j, 0, n)
			{
				if (!used[j] && (v == -1 || cmp(bestPath[j], bestPath[v])))
				{
					v = j;
				}
			}
		}
		used[v] = 1;
		VI path = bestPath[v];
		for (int i : g[v])
		{
			int to = edges[i].v;
			path.PB(i);
			if (cmp(path, bestPath[to]))
			{
				bestPath[to] = path;
			}
			path.pop_back();
		}
	}
	FOR(v, 0, n)
	{
		cout << SZ(bestPath[v]) + 1 << " " << s + 1;
		for (int i : bestPath[v])
			cout << " " << edges[i].v + 1;
		cout << "\n";
	}
	return 0;
}