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

struct Edge {
    int to;
    int l; 
    int p; 
};

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

    string A;
    cin >> A;

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

    vector<vector<int>> bestPath(n);  // Best path to each node
    bestPath[s].push_back(s);  // Start with the source node

    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (const auto& edge : adj[curr]) {
            int next = edge.to;
            vector<int> candidatePath = bestPath[curr];  // Copy the current best path
            candidatePath.push_back(next);

            if (bestPath[next].empty() || lexicographical_compare(candidatePath.begin(), candidatePath.end(), bestPath[next].begin(), bestPath[next].end())) {
                bestPath[next] = candidatePath;  // Update with the better path
                q.push(next);
            }
        }
    }


    for (int i = 0; i < n; i++) {
        if (bestPath[i].empty()) {
            cout << "0\n";
        } else {
            cout << bestPath[i].size() << " ";
            for (int node : bestPath[i]) cout << node + 1 << " ";
            cout << "\n";
        }
    }

    return 0;
}