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

struct Edge {
    int v, p, l;
    string label;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, d, s;
    cin >> n >> m >> d >> s;

    string A;
    cin >> A;

    vector<vector<Edge>> graph(n+1);
    for (int i = 0; i < m; i++) {
        int u, v, p, l;
        cin >> u >> v >> p >> l;
        graph[u].push_back({v, p-1, l, A.substr(p-1, l)});
    }

    auto findShortestPath = [&](int start, int end) {
        vector<vector<pair<string, vector<int>>>> dist(n+1);
        priority_queue<
            pair<pair<int, string>, vector<int>>, 
            vector<pair<pair<int, string>, vector<int>>>, 
            greater<pair<pair<int, string>, vector<int>>>
        > pq;

        pq.push({{0, ""}, {start}});

        while (!pq.empty()) {
            auto [info, path] = pq.top(); 
            pq.pop();
            int curr = path.back();
            
            if (curr == end) return path;
            
            for (auto& edge : graph[curr]) {
                vector<int> newPath = path;
                newPath.push_back(edge.v);
                string newStr = info.second + edge.label;
                
                if (dist[edge.v].empty() || 
                    make_pair(newPath.size(), newStr) < 
                    make_pair(dist[edge.v][0].second.size(), dist[edge.v][0].first)) {
                    dist[edge.v] = {{newStr, newPath}};
                    pq.push({{newPath.size(), newStr}, newPath});
                }
            }
        }
        
        return vector<int>();
    };

    for (int i = 1; i <= n; i++) {
        auto path = findShortestPath(s, i);
        
        if (path.empty()) {
            cout << "0\n";
        } else {
            cout << path.size() << " ";
            for (int node : path) cout << node << " ";
            cout << "\n";
        }
    }

    return 0;
}