problem 1463.

#include<iostream.h>
int a[50000],b[50000],c[50000],rad[50000],n,m,st;
int max,maxi[50000],maxn=0;
struct stag{
    int ver,reb;

};

void prov(int k1)
{
int i=1,n1=1,i1=1,pp=0,pr[50000],k;
stag st[50000];
int sum=rad[k1];

for(i=1;i<=n;i++)pr[i]=0;
st[n1].ver=k1;

while(n1>0)
{
k=st[n1].ver;pp=0;
for(i=i1;i<=m;i++)
if((pr[i]==0)&&((k==a[i])||(k==b[i])))
{
st[n1].reb=i;
n1++;
if(k==a[i])st[n1].ver=b[i];else st[n1].ver=a[i];
pr[i]=1;
if(k==a[i])sum+=c[i]+rad[b[i]];else sum+=c[i]+rad[a[i]];
if(max<=sum)
{
max=sum;
maxn=n1;
for(int j=1;j<=n1;j++)maxi[j]=st[j].ver;
}

pp=1;
break;
}


if(st[n1-1].reb<0)st[n1-1].reb=0;
if(pp==0){i=st[n1-1].reb;i1=i+1;pr[i]=0;n1--;
if(n1>0)sum-=(c[i]+rad[k]);}else i1=1;
}
}
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i++)cin>>rad[i];

for(i=1;i<=m;i++)
cin>>a[i]>>b[i]>>c[i];


for(i=1;i<=n;i++)
prov(i);

cout<<max<<endl;
if(n==1)maxn=1;
cout<<maxn<<endl;
for(i=1;i<=maxn;i++)cout<<maxi[i]<<" ";

return 0;
}