#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct Edge{
    int nex;
    int l;
    int r;
};

const int N = 610;
const int MOD = (int)1e9 + 9;
const int B = 77;
const int L = (int)1e6 + 10;
int d;

int id[L];
int pwr[L];
int cum[L];

vector<Edge> E[N];

int get_hash(int l, int r){
    int sum = (cum[r] - cum[l - 1] + MOD) % MOD;
    return (sum * 1ll * pwr[d - r]) % MOD;
}

bool is_equal(int l1, int r1, int l2, int r2){
    return get_hash(l1,r1) == get_hash(l2,r2);
}

int ci = 0;

bool cmp(vector<Edge> A, vector<Edge> B){ // is A < B
    int i = 0, j = 0;
    ci ++ ;
    while(i < A.size() && j < B.size()){
        int len = min(A[i].r - A[i].l, B[j].r - B[j].l) + 1;
        if(is_equal(A[i].l, A[i].l + len - 1, B[j].l, B[j].l + len - 1)){
            A[i].l += len;
            B[j].l += len;
            if(A[i].l > A[i].r) i ++ ;
            if(B[j].l > B[j].r) j ++ ;
        }
        else{
            // find the difference point with binary search and then just compare (;
            int lf = 0, rf = len - 1;
            while(lf < rf){
                int mid = (lf + rf) / 2;
                if(is_equal(A[i].l, A[i].l + mid, B[j].l, B[j].l + mid)){
                    lf = mid + 1;
                }
                else{
                    rf = mid;
                }
            }
            int ii = A[i].l + lf;
            int jj = B[j].l + lf;
            if(id[ii] < id[jj]) return true;
            else return false;
        }
    }
    if(j == B.size()){
        return false;
    }
    else{
        return true;
    }
}

struct Path{
    vector<Edge> P;
    bool operator< (const Path &E) const {
        return cmp(P, E.P);
    }
};

struct State{
    int node;
    Path P;
    bool operator< (const State &A) const {
        return cmp(A.P.P, P.P);
    }
};

Path low[N];
bool vis[N];

int main(){
    fastIO;
    int n, m, s;
    cin >> n >> m >> d >> s;
    int u, v, l, r;
    pwr[0] = 1;
    for(int i = 1; i <= d; i ++ ){
        char f;
        cin >> f;
        id[i] = f - 'a' + 1;
        pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
        cum[i] = (cum[i - 1] + (pwr[i] * 1ll * id[i]) % MOD) % MOD;
    }
    for(int i = 1; i <= m ; i ++ ){
        cin >> u >> v >> l >> r;
        r = r + l - 1;
        E[u].push_back({v, l, r});
    }
    priority_queue<State> si;
    si.push({s, {{}}});
    while(!si.empty()){
        State cur = si.top();
        si.pop();
        if(vis[cur.node]) continue;
        vis[cur.node] = true;
        for(auto e : E[cur.node]){
            Path nw = cur.P;
            nw.P.push_back({e.nex, e.l, e.r});
            if(low[e.nex].P.empty() || nw < low[e.nex]){
                low[e.nex] = nw;
                si.push({e.nex, low[e.nex]});
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << low[i].P.size() + 1 << " ";
        cout << s << " ";
        for(auto x : low[i].P){
            cout << x.nex << " ";
        }
        cout << "\n";
    }
    return 0;
}