#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N = 510, inf = 0x3f3f3f3f;

int cmax, n, sp, m;
int store[N], g[N][N], dist[N];
bool st[N];
vector<int> pre[N];
vector<int> path, anspath;
int minback = inf, minsend = inf;

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;

    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 0; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        for (int j = 0; j <= n; j++)
        {
            if (dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];   
                pre[j].clear();
                pre[j].push_back(t);
            }
            else if (dist[j] == dist[t] + g[t][j])
            {
                pre[j].push_back(t);
            }
        }
    }
}

void dfs(int u)
{
    path.push_back(u);
    if (u == 0)
    {
        int tback = 0, tsend = 0;
        //倒序为了从PBMC到目标点正向遍历
        for (int i = path.size() - 1; i >= 0; i--)
        {
            int p = path[i];

            if (store[p] > 0)   //当前点为正数：超过cmax / 2
                tback += store[p];
            else if (store[p] < 0)  //当前点为负数：小于cmax / 2，需要补充车辆
            {
                if (tback >= -store[p]) //之前多余出来的车能把这里缺的数量补上
                    tback -= -store[p];
                else    //补不上，需要从PBMC带车过来
                {
                    tsend += -store[p] - tback;
                    tback = 0;
                }
            }
        }
        if (tsend < minsend)
        {
            minsend = tsend;
            minback = tback;
            anspath = path;
        }
        else if (tsend == minsend && tback < minback)
        {
            minsend = tsend;
            minback = tback;
            anspath = path;
        }

        path.pop_back();
        return ;
    }
    for (int i = 0; i < pre[u].size(); i++)
        dfs(pre[u][i]);

    path.pop_back();
    return ;
}

int main()
{
    cin >> cmax >> n >> sp >> m;
    for (int i = 1; i <= n; i++) 
    {
        int a;
        cin >> a;
        store[i] = a - cmax / 2;
    }

    memset(g, 0x3f,sizeof g);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    dijkstra();

    dfs(sp);

    cout << minsend << " ";
    for (int i = anspath.size() - 1; i >= 0; i--)
    {
        cout << anspath[i];
        if (i != 0) cout << "->";
    }
    cout << " " << minback;
    return 0;
}