/* Jozef Tvarozek - Save the trees! */
#include <stdio.h>

#define MAXN 32
#define MAXL 50000

typedef struct
{
  int sofar,next_best,ttl;
  char use[MAXN];
  char npath,path[MAXN+MAXN+1];
} ITEM;

typedef struct
{
  int val,i;
} CITY;

int g[MAXN][MAXN],bim[MAXN];
int n,best=999999999;
ITEM bitem;
ITEM q[MAXL];
int head,tail;
int gtim=1;

CITY c[MAXN];

int next_best(ITEM item)
{
  int i,j=0,k=1;
  for (i = 0; i < n; i++)
    if ( item.use[c[i].i] == 0 )
    {
      j += k*c[i].val;
      k++;
    }
  return j;
}
void print(void)
{
  int i,j;
  printf("\nbest = %d\n",best);
  for (i = head; i < tail; i++)
  {
    printf("val=%d,nb=%d: ",q[i].sofar,q[i].next_best);
    for (j = 0; j < q[i].npath; j++)
      printf("%d,",q[i].path[j]+1);
    printf("\n");
  }
  getchar();
}
int addkill(char *use)
{
  int i,j=0;
  for (i = 0; i < n; i++)
    if ( use[i] == 0 )
      j += bim[i];
  return j;
}
int better(ITEM a,ITEM b)
{
  int i;
  if ( a.path[a.npath-1] != b.path[b.npath-1] )
    return 0;
  for (i = 0; i < n; i++)
    if ( a.use[i] != b.use[i] )
      return 0;
  if ( a.sofar < b.sofar )
    return 1;
  if ( a.sofar > b.sofar )
    return 0;
  if ( a.npath < b.npath )
    return 1;
  return 0;
}

void additem(ITEM item)
{
  int i;
  if ( item.next_best > best )
    return;
  for (i = 0; i < tail; i++)
    if ( better(q[i],item) )
      break;
  for (i = 0; i < n; i++)
    if ( item.use[i] == 0 )
      break;
  if ( i == n )
  {
    if ( best > item.sofar || ( best == item.sofar && bitem.npath > item.npath ) )
    {
      best = item.sofar;
      bitem = item;
    }
    return;
  }
/*  if ( tail == MAXL )
  {
    printf("overflow (head=%d)\n",head);
    getchar();
    exit(0);
  }
*/
  if ( tail < MAXL )
    q[tail++] = item;
}
void addnext(ITEM item)
{
  ITEM nitem;
  int i;

  if ( item.npath >= n+n )
    return;
  nitem = item;
  for ( i = 0; i < n; i++)
    if ( g[item.path[item.npath-1]][i] )
    {
      nitem = item;
      nitem.path[nitem.npath++] = i;
      nitem.sofar += addkill(nitem.use);
      nitem.use[i] = 1;
      nitem.next_best = nitem.sofar + next_best(nitem);
      nitem.ttl = gtim++;
      additem(nitem);
    }
}
int city_cmp(const void *va, const void *vb)
{
  CITY *ca=(CITY*)va, *cb=(CITY*)vb;
  if ( ca->val > cb->val ) return -1;
  return 1;
}

int main(void)
{
  FILE *fin,*fout;
  ITEM tmp;
  int i,m,j,k;

  fin = fopen("tre.in","rt");
  fout = fopen("tre.out","wt");

  fscanf(fin,"%d %d",&n,&m);
  for (i = 0; i < n; i++)
  {
    fscanf(fin,"%d",&bim[i]);
    c[i].i = i;
    c[i].val = bim[i];
  }
  bim[0] = 0;
  c[0].val = 0;
  qsort(&c,n,sizeof(CITY),city_cmp);
  for (i = 0; i < m; i++)
  {
    fscanf(fin,"%d %d",&j,&k);
    g[j-1][k-1] = 1;
    g[k-1][j-1] = 1;
  }
  tail = 1;
  q[0].sofar = 0;
  q[0].path[0] = 0;
  q[0].npath = 1;
  q[0].use[0] = 1;
  q[0].next_best = next_best(q[0]);
  q[0].ttl = gtim++;

//  print();
  while ( head != tail )
  {
    j = head;
    for (i = head+1; i < tail; i++)
      if (( q[i].next_best < q[j].next_best ) || ( q[i].next_best == q[j].next_best && q[i].ttl > q[j].ttl ))
        j = i;
    if ( j != head )
    {
      tmp = q[head];
      q[head] = q[j];
      q[j] = tmp;
    }
    if ( q[head].next_best >= best )
      break;
//    if ( rand () % 100 == 0 )
//    printf("\r%3d,%3d [%05d-%05d]",q[head].sofar,q[head].next_best,head,tail);
    addnext(q[head]);
//    print();
    head++;
  }
  fprintf(fout,"%d %d\n1",best,bitem.npath-1);
  for (i = 1; i < bitem.npath; i++)
    fprintf(fout," %d",bitem.path[i]+1);
  fprintf(fout,"\n");
/*  printf("%d %d\n1",best,bitem.npath-1);
  for (i = 1; i < bitem.npath; i++)
    printf(" %d",bitem.path[i]+1);
  printf("\n");
  */
  return 0;
}
