#include<iostream>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int c, n, s, m, aa[501][501], bb[501], num[501];
bool flag[501] = { false };
int anss = INF, ansb = INF;
vector<int>temp, ans, pre[501];

void dfs(int node, int need, int cap)
{
	if ((node == 0) && ((need < anss) || (need == anss && cap < ansb)))
	{
		anss = need, ansb = cap;
		ans.clear();
		for (auto it = temp.begin(); it != temp.end(); it++)
			ans.push_back(*it);
	}
	temp.push_back(node);
	for (int i = 0; i < pre[node].size(); i++)
	{
		int dif = need - num[pre[node][i]];
		dfs(pre[node][i], dif >= 0 ? dif : 0, dif >= 0 ? cap : cap - dif);
	}
	temp.erase(temp.end() - 1);
}

int main()
{
	scanf("%d %d %d %d", &c, &n, &s, &m);
	fill(aa[0], aa[0] + 501 * 501, INF);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &num[i]);
		num[i] = num[i] - c / 2;
	}
	for (int i = 0, a, b, l; i < m; i++)
	{
		scanf("%d %d %d", &a, &b, &l);
		aa[a][b] = aa[b][a] = l;
	}

	fill(bb, bb + 501, INF);
	bb[0] = 0;
	while (true)
	{
		int val = INF, id;
		for (int i = 0; i <= n; i++)
			if (!flag[i] && bb[i] < val)
				val = bb[i], id = i;
		if (val == INF || id == s) break;
		flag[id] = true;

		for (int i = 0; i <= n; i++)
		{
			if (!flag[i] && val + aa[id][i] < bb[i])
			{
				bb[i] = val + aa[id][i];
				pre[i].clear();
				pre[i].push_back(id);
			}
			else if (!flag[i] && val + aa[id][i] == bb[i])
				pre[i].push_back(id);
		}
	}
	dfs(s, num[s] >= 0 ? 0 : -num[s], num[s] >= 0 ? num[s] : 0);

	printf("%d 0", anss);
	for (int i = ans.size() - 1; i >= 0; i--)
		printf("->%d", ans[i]);
	printf(" %d", ansb);

	return 0;
}