/*
Data: 2019-04-20 19:10:26
Problem: PAT_A1018#Public Bike Management
AC: 34:36
题目大意：
站点最佳状态时，有一半的自行车；
从起点选择最短路径终点，路径上的其他站点同样调整至最佳状态（补充/回收）；
多条最短路径时，选择需要携带且回收数量最少的最条路径
输入：
第一行给出，最大容量Cmax，结点数N，Sp终点（默认起点为0），路径数M
第二行给出，各站点现有库存Ci
输出；
携带车辆数，路径，回收车辆数
*/
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int M=,INF=1e9;
int grap[M][M],vis[M],d[M],c[M];
int n,m,Cmax,st=,dt,optSent=INF,optBring=INF;
vector<int> temp,opt,pre[M];
void Dijskra(int s)
{
fill(vis,vis+M,);
fill(d,d+M,INF);
d[s]=;
for(int i=; i<=n; i++)
{
int u=-,Min=INF;
for(int j=; j<=n; j++)
{
if(vis[j]== && d[j]<Min)
{
u=j;
Min=d[j];
}
}
if(u==-) return;
vis[u]=;
for(int v=; v<=n; v++)
{
if(vis[v]== && grap[u][v]!=INF)
{
if(d[u]+grap[u][v] < d[v])
{
d[v]=d[u]+grap[u][v];
pre[v].clear();
pre[v].push_back(u);
}
else if(d[u]+grap[u][v]==d[v])
pre[v].push_back(u);
}
}
}
}
void DFS(int v)
{
if(v == st)
{
int sent=,bring=;
for(int i=temp.size()-; i>=; i--)
{
int v = temp[i];
if(bring+(c[v]-Cmax/) > )
bring = bring + (c[v]-Cmax/);
else
{
sent += (Cmax/-bring-c[v]);
bring=;
}
}
if(sent < optSent)
{
optSent = sent;
optBring = bring;
opt = temp;
}
else if(sent==optSent && bring<optBring)
{
optBring = bring;
opt = temp;
}
return;
}
temp.push_back(v);
for(int i=; i<pre[v].size(); i++)
DFS(pre[v][i]);
temp.pop_back();
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE
fill(grap[],grap[]+M*M,INF);
scanf("%d%d%d%d", &Cmax,&n,&dt,&m);
for(int i=; i<=n; i++)
scanf("%d", &c[i]);
for(int i=; i<m; i++)
{
int v1,v2;
scanf("%d%d",&v1,&v2);
scanf("%d", &grap[v1][v2]);
grap[v2][v1]=grap[v1][v2];
}
Dijskra(st);
DFS(dt);
printf("%d %d", optSent,st);
for(int i=opt.size()-; i>=; i--)
printf("->%d", opt[i]);
printf(" %d", optBring);
return ;
}