#include <bits/stdc++.h>

using namespace std;

#define DIM 100009
#define INF 100000000000009

struct edge{
    long long to,mas,num;
};

long long a[DIM],b[DIM],c[DIM],road[DIM];

pair<long long,long long>way[DIM];

vector<long long>res;

vector<edge>g[DIM];

priority_queue< pair<long long,long long>,vector< pair<long long,long long> >,greater< pair<long long,long long> > >q;

long long n,m,i,j,k,l,start,finish,x,y,v,money,kilkroad;

int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>c[i];
    }

    start=1;finish=n;

    for(i=1;i<=m;i++){
        cin>>k>>l>>j>>v;
        if(j==1){
            money+=v;
            road[i]=1;
        }
//        cout<<v<<' '<<money<<' '<<j<<' '<<finish<<' '<<1<<endl;
        g[k].push_back({l,l+c[j],i});
        g[l].push_back({k,k+c[j],i});
    }
    memset(a,0,sizeof(a));
    for(i=0;i<DIM-4;i++)b[i]=INF;
    b[start]=0;
    q.push({0,start});
    long long w;
    while(!q.empty()){
        v=q.top().second;
        q.pop();
        if(a[v]==1)continue;
        a[v]=1;
        for(i=0;i<g[v].size();i++){
            x=g[v][i].to;
            y=g[v][i].mas;
            w=g[v][i].num;
            if(b[x]>b[v]+y){
                b[x]=b[v]+y;
                way[x]={v,w};
                q.push({b[x],x});
            }
        }
    }

    w=finish;
  //  cout<<b[finish]<<' '<<money<<endl;
    if(b[finish]>money){
            cout<<-1<<endl;
            return 0;
    }

    while(w!=1){
        res.push_back(w);
        road[way[w].second]+=2;
        w=way[w].first;
    }

    res.push_back(1);

    reverse(res.begin(),res.end());

    for(i=1;i<=m;i++){
        if(road[i]==1)kilkroad++;
    }
    cout<<kilkroad<<' ';
    for(i=1;i<=m;i++){
        if(road[i]==1){
            cout<<i<<' ';
        }
    }
    cout<<endl;
    kilkroad=0;
    for(i=1;i<=m;i++)
        if(road[i]==2)kilkroad++;

    cout<<kilkroad<<' ';

    for(i=1;i<=m;i++){
        if(road[i]==2)cout<<i<<' ';
    }

    cout<<endl;

    for(i=0;i<res.size();i++){
        cout<<res[i]<<' ';
    }
    cout<<endl;
    return 0;
}