1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=520,inf=~0u>>2;
 6 
 7 int n,m,s,t,a[N];
 8 int mp[N][N];
 9 int vis[N],d[N],peo[N],pre[N],cnt[N];
10 
11 
12 void dij()
13 {
14     F(i,0,n-1)vis[i]=0,d[i]=inf;
15     d[s]=0;
16     pre[s]=-1;
17     cnt[s]=1,peo[s]=a[s];
18     F(i,0,n-1)
19     {
20         int mi=inf,p=-1;
21         F(j,0,n-1)if(!vis[j]&&mi>d[j])mi=d[p=j];
22         if(p==-1)continue;
23         vis[p]=1;
24         F(j,0,n-1)if(vis[j]==0&&mp[p][j]!=inf)
25         {
26             if(d[j]>d[p]+mp[p][j])
27             {
28                 d[j]=d[p]+mp[p][j];
29                 peo[j]=a[j]+peo[p];
30                 pre[j]=p;
31                 cnt[j]=cnt[p];
32             }else if(d[j]==d[p]+mp[p][j])
33             {
34                 cnt[j]+=cnt[p];
35                 if(peo[j]<a[j]+peo[p])
36                 {
37                     peo[j]=a[j]+peo[p];
38                     pre[j]=p;
39                 }
40             }
41         }
42     }
43 }
44 
45 int main()
46 {
47     scanf("%d%d%d%d",&n,&m,&s,&t);
48     F(i,0,n-1)scanf("%d",a+i);
49     F(i,0,n)F(j,0,n)mp[i][j]=(i==j?0:inf);
50     F(i,1,m)
51     {
52         int a,b,c;
53         scanf("%d%d%d",&a,&b,&c);
54         mp[a][b]=min(c,mp[a][b]);
55         mp[b][a]=mp[a][b];
56     }
57     dij();
58     printf("%d %d\n",cnt[t],peo[t]);
59     int path[N],ed=0;
60     for(int i=t;~i;i=pre[i])path[++ed]=i;
61     for(int i=ed;i>0;i--)printf("%d%c",path[i],i==1?‘\n‘:‘ ‘);
62     return 0;
63 }