#include<iostream>

 #include<algorithm>

 #include<vector>

 #include<string.h>

 using namespace std;

 const int M = 0x3f3f3f3f;

 int c, n, sp, m;

 int mat[][];

 int vis[];                        //第一次用于作为求dist记录该点是否到达 第二次用于深搜回溯记录是否走过该点

 int num[];

 int dist[];

 int les_dist = M;

 struct Node{

     int need;

     int rest;

     int distance;

     vector<int> road;

 };

 vector<Node> r;                        //用于存放多个最短路情况下的行走方案，一个数据结构存放一个方案的信息

 int minn(){

     int k = -;

     int Min = M;

     int i;

     for(i = ; i <= n; i++){

         if(vis[i] ==  && dist[i] < Min){

             Min = dist[i];

             k = i;

         }

     }

     return k;

 }

 void run1(){

     int i;

     for(i = ; i <= n; i++){        //将从0点开始到其他点的距离设为到该点的最小值

         dist[i] = mat[][i];

     }

     for(i = ; i <= n; i++){        //包含0点则有n+1个点 需要进行n次查询

         int k = minn();

         if(k == -) break;            //查询次数未用完但k==-1则代表图不连通 退出循环

         vis[k] = ;

         int j;

         for(j = ; j <= n; j++){

             if(vis[j] ==  && dist[k] + mat[k][j] < dist[j]){

                 dist[j] = dist[k] + mat[k][j];

             }

         }

     }

     les_dist = dist[sp];            //全局变量les_dist存放到达终点的最短路径

 }

 void dfs(Node s, int x){

     //对于当前点x来说 需要判断此时存放路径数据的长度加到达x的长度和最短路径长度的关系

     int pre = s.road.back();    //前一个点

     if(s.distance + mat[pre][x] <= les_dist){

         s.distance += mat[pre][x];

         if(num[x] < c/){        //需要对该点的自行车的数量进行调整

             if(s.rest >= c/ - num[x]){

                 s.rest -= (c/ - num[x]);

             }else{                //剩余的不够

                 s.need += c/ - num[x] - s.rest;    //需要的总数减去有的总数则为需要从0点发出的数量

                 s.rest = ;

             }

         }else if(num[x] > c/){

             s.rest += num[x] - c/;    //对多余的车都放入rest中

         }

         s.road.push_back(x);    //将x加入已经走过的点的队列

         //当点加完之后判断是否到了终点

         if(x == sp){

             r.push_back(s);        //将s这个路径选择方案加入vector r

         }

     }

     if(sp == x) return;

     vis[x] = ;

     int i;

     for(i = ; i <= n; i++){

         if(vis[i] ==  && mat[x][i] != M){

             dfs(s, i);

             vis[i] = ;

         }

     }

 }

 bool cmp(Node a, Node b){

     if(a.need != b.need) a.need < b.need;

     else{

         return a.rest < b.rest;

     }

 }

 void run2(){

     memset(vis, , sizeof(vis));    //此次的vis需要重新清零

     Node s;

     s.need = ;

     s.rest = ;

     s.distance = ;

     s.road.push_back();            //将0点作为起始点

     dfs(s, );                        //从0点开始 其中s为当前存放路径数据的数据结构

     sort(r.begin(), r.end(), cmp);

     Node ans = r.front();

     if(sp != ){

         printf("%d ", ans.need);

         int i;

         for(i = ; i < ans.road.size(); i++){

             if(i != ) printf("->");

             printf("%d", ans.road[i]);

         }

         printf(" %d\n", ans.rest);

     }else{

         printf("0 0 0\n");

     }

 }

 int main(){

     scanf("%d%d%d%d", &c, &n, &sp, &m);

     memset(mat, M, sizeof(mat));

     memset(vis, , sizeof(vis));

     int i;

     for(i = ; i <= n; i++){        //输入没个点的自行车数量

         scanf("%d", &num[i]);

     }

     for(i = ; i < m; i++){

         int x, y, z;

         scanf("%d%d%d", &x, &y, &z);

         mat[x][y] = z;

         mat[y][x] = z;

     }

     run1();                            //这部分完成了从起点到sp点的最短路径的计算

     run2();                            //通过bfs查询出通路然后加入vector

     return ;

 }