#include<stdio.h>#include<stack>using namespace std;int bike_count[510];int bike_sum[510]; int bike_sum_num[510];int map[510][510];bool visited[510];int d[510];int pre[510];int Max=0xffffffff>>1;//max=max>>1;int findMin(int n){    int min=Max,index=-1;    for(int i=0;i<=n;i++)    {      if(!visited[i]&&d[i]<min)      {          min=d[i];          index=i;      }    }    return index;} int main(){     int maxc,n,sp,m;     int a,b,val;     freopen("1018-in.txt","r",stdin);     freopen("1018-out.txt","w",stdout);     while(scanf("%d%d%d%d",&maxc,&n,&sp,&m)!=EOF)     {       for(int i=0;i<=n;i++)//init map         {          for(int j=0;j<=n;j++)          {             map[i][j]=Max;          }          visited[i]=false;          d[i]=Max;          bike_sum[i]=0;          bike_sum_num[i]=0;          pre[i]=0;        }        bike_count[0]=0;        for(int i=1;i<=n;i++)        {          scanf("%d",&bike_count[i]);        }                for(int i=0;i<m;i++)        {          scanf("%d%d%d",&a,&b,&val);          map[a][b]=map[b][a]=val;        }                //begin dijkstra        int index;        d[0]=0;        pre[0]=-1;         while(true)         {            index=findMin(n);            //for(int s=0;s<n;s++)             // printf("%d ",d[s]);             //("\n");            visited[index]=true;            //printf("index=%d\n",index);            if(index==-1)              break;            for(int i=0;i<=n;i++)            {              if(map[i][index]!=Max&&d[i]>d[index]+map[index][i])              {                 d[i]=d[index]+map[index][i];                 bike_sum[i]=bike_sum[index]+bike_count[i];                 bike_sum_num[i]=bike_sum_num[index]+1;                 pre[i]=index;                 //printf( "0 i=%d,index=%d %d\n",i,index,bike_sum[i]);              }              else if(map[i][index]!=Max&&d[i]==d[index]+map[index][i])              {                 double a=(bike_sum[i]/(bike_sum_num[i]*1.0));                 double b=(bike_sum[index]+bike_count[i])/((bike_sum_num[index]+1)*1.0);                 //printf("%lf %lf\n",a,b);                 if(a>maxc/2.0&&b>=maxc/2.0&&a>b)                 {                      d[i]=d[index]+map[index][i];                      bike_sum[i]=bike_sum[index]+bike_count[i];                      bike_sum_num[i]=bike_sum_num[index]+1;                      pre[i]=index;                      //printf("1 i=%d,index=%d,%d\n",i,index,bike_sum[i]);                 }                 if(a<maxc/2.0&&b<=maxc/2.0&&a<b)                 {                      d[i]=d[index]+map[index][i];                      bike_sum[i]=bike_sum[index]+bike_count[i];                      bike_sum_num[i]=bike_sum_num[index]+1;                      pre[i]=index;                      //printf("2 i=%d,index=%d,%d\n",i,index,bike_sum[i]);                 }                  if(a<maxc/2.0&&b>=maxc/2.0)                 {                      d[i]=d[index]+map[index][i];                      bike_sum[i]=bike_sum[index]+bike_count[i];                      bike_sum_num[i]=bike_sum_num[index]+1;                      pre[i]=index;                      //printf("3 i=%d,index=%d,%d\n",i,index,bike_sum[i]);                 }                 /*if(b==maxc/2.0)                 {                      d[i]=d[index]+map[index][i];                      bike_sum[i]=bike_sum[index]+bike_count[i];                      bike_sum_num[i]=bike_sum_num[index]+1;                      pre[i]=index;                 }*/                 //printf("4 i=%d,index=%d,%d\n",i,index,bike_sum[i]);              }            }         }//while(true)         //printf("%d\n",bike_sum[sp]);          //printf("%d\n",bike_sum_num[sp]);           int mod=bike_sum_num[sp]*maxc/2-bike_sum[sp];          printf("%d ",mod>=0?mod:0);          int p=sp;          stack<int> path;          path.push(sp);          while(true)          {             p=pre[p];             if(p==-1)               break;             path.push(p);          }          while(!path.empty())          {              printf("%d",path.top());              if(path.size()!=1)               printf("->");              path.pop();          }              printf(" %d\n",mod<=0?0-mod:0);     }    return 0;}