#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, d, s;
    cin >> n >> m >> d >> s;

    string A;  //all edge labels are substrings of A
    cin >> A;

    vector<pair<string, int>> adj[n+1]; //target, substring
    for (int i = 0; i < m; i++) {
        int u, v, p, l;
        cin >> u >> v >> p >> l;
        adj[u].push_back({A.substr(p-1, l), v});
    }

    for (int i = 1; i <= n; i++) {
        vector<pair<string, vector<int>>> wrk;
        vector<pair<string, vector<int>>> cmp;

        wrk.push_back({"",{s}});

        while (!wrk.empty()) {
            vector<pair<string, vector<int>>> cwrk;
            for (auto [s, vec] : wrk) {
                int ln = vec.back();
                if (ln == i) {
                    cmp.push_back({s, vec});
                } else for (auto [newS, v] : adj[ln]) {
                    vector<int> tmp = vec;
                    tmp.push_back(v);
                    cwrk.push_back({s+newS, tmp});
                }
            }
            wrk = cwrk;
        }
        if (cmp.empty()) {
            cout << 0;
        } else {
            auto [_, bestPath] = *min_element(cmp.begin(), cmp.end());
            cout << bestPath.size() << " ";
            for (auto node : bestPath) cout << node << " ";
        }
        cout << "\n";
    }
    return 0;
}