#include<bits/stdc++.h>

 using namespace std;

 const int inf = 1e9;

 int c,n,s,m;

 int a[];//每个站初始自行车数量

 vector<pair<int,int> >adj[];//邻接表

 int d[];//最短路距离

 bool inq[];//是否在队列中的标记

 vector<int>pre[];//前驱结点数组

 vector<int>path,temp_path;

 int sent=inf,take=inf;

 void SPFA(){

     queue<int>q;

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

         d[i]=inf;

     q.push();

     inq[]=true;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         inq[u]=false;

         for(int i=;i<adj[u].size();++i){

             int v=adj[u][i].first;

             int val=adj[u][i].second;

             if(!v)

                 continue;

             if(d[u]+val<d[v]){

                 d[v]=d[u]+val;

                 pre[v].clear();

                 pre[v].push_back(u);

                 if(!inq[v]){

                     q.push(v);

                     inq[v]=true;

                 }

             }

             else if(d[u]+val==d[v])

                 pre[v].push_back(u);

         }

     }

 }

 void DFS(int x){

     if(!x){

         int remain=,temp_sent=;

         temp_path.push_back(x);

         for(int i=temp_path.size()-;i>=;--i){

             int u=temp_path[i];

             remain+=a[u]-c/;

             if(remain<){

                 temp_sent-=remain;

                 remain=;

             }

         }

         if(temp_sent<sent){

             path=temp_path;

             sent=temp_sent;

             take=remain;

         }

         else if(temp_sent==sent&&remain<take){

             path=temp_path;

             take=remain;

         }

         temp_path.pop_back();

     }

     temp_path.push_back(x);

     for(int i=;i<pre[x].size();++i)

         DFS(pre[x][i]);

     temp_path.pop_back();

 }

 int main(){

     cin>>c>>n>>s>>m;

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

         cin>>a[i];

     int u,v,val;

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

         cin>>u>>v>>val;

         adj[u].push_back({v,val});

         adj[v].push_back({u,val});

     }

     SPFA();

     DFS(s);

     cout<<sent<<" ";

     for(int i=path.size()-;i>=;--i){

         if(i<path.size()-)

             cout<<"->";

         cout<<path[i];

     }

     cout<<" "<<take;

     return ;

 }