求助，求HACK

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 500010
#define N (ll)1e18
#define debug cout<<"flyfree\n";
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct node_line{
	ll k,b,id;
	ll find(ll x){
		return k*x+b; 
	}
};
struct node_LCsagment{
	set <ll> pnt[MAXN*4];
	node_line ln[MAXN*4];
	ll minz[MAXN*4],l[MAXN*4],r[MAXN*4];
	void push_up(ll now){//修改 
		if(!pnt[now].size()){
			minz[now]=N;
			return;
		}
		ll lz=*(pnt[now].begin()),rz=*(--pnt[now].end());
//		cout<<"push_up: "<<l[now]<<" "<<r[now]<<" "<<lz<<" "<<rz<<endl;
		minz[now]=min(min(ln[now].find(lz),ln[now].find(rz)),min(minz[now*2],minz[now*2+1]));
	}
	void insert(ll lz,ll rz,ll now,node_line val){//加边 
		if(!pnt[now].size()){
			minz[now]=N;
			return;
		}
		ll mid=(l[now]+r[now])/2;
		if(l[now]>=lz&&r[now]<=rz){
			ll _l=*(pnt[now].begin()),_r=*(--pnt[now].end());
			if(val.find(mid)<ln[now].find(mid))swap(ln[now],val);
			if(l[now]==r[now]){
				minz[now]=ln[now].find(l[now]);
//				cout<<"insert: "<<l[now]<<" "<<r[now]<<" "<<minz[now]<<endl;
				return;
			}
			if(pnt[now*2].size()&&val.find(_l)<ln[now].find(_l))insert(lz,rz,now*2,val);
			if(pnt[now*2+1].size()&&val.find(_r)<ln[now].find(_r))insert(lz,rz,now*2+1,val);
			push_up(now);
			return;
		}
		if(lz<=mid)insert(lz,rz,now*2,val);
		if(rz>mid)insert(lz,rz,now*2+1,val);
		push_up(now);
//		cout<<"insert: "<<l[now]<<" "<<r[now]<<" "<<minz[now]<<endl;
	}
	void push_down(ll now){
		if(pnt[now*2].size()>0&&(ln[now*2].k!=ln[now].k||ln[now*2].b!=ln[now].b)){
			insert(l[now*2],r[now*2],now*2,ln[now]);
		}
		if(pnt[now*2+1].size()>0&&(ln[now*2+1].k!=ln[now].k||ln[now*2+1].b!=ln[now].b)){
			insert(l[now*2+1],r[now*2+1],now*2+1,ln[now]);
		}
	}
	void build(ll lz,ll rz,ll now){//建树 
		l[now]=lz,r[now]=rz,minz[now]=N;
		for(int i=lz;i<=rz;i++)pnt[now].insert(i);
		ln[now]=(node_line){0,N};
		if(lz==rz)return;
		ll mid=(lz+rz)/2;
		build(lz,mid,now*2);
		build(mid+1,rz,now*2+1);
	}
	void del(ll pos,ll now){//删点 
		pnt[now].erase(pos);
		if(l[now]==r[now]){
			minz[now]=N;
			return;
		}
		push_down(now);
		ll mid=(l[now]+r[now])/2;
		if(pos<=mid)del(pos,now*2);
		else del(pos,now*2+1);
		push_up(now);
	}
	ll find(ll now){//找最低点 
		if(l[now]==r[now]){
			return l[now];
			
		}
		push_down(now);
		push_up(now);
//		cout<<"find: "<<l[now]<<" "<<r[now]<<" "<<minz[now*2]<<" "<<minz[now*2+1]<<endl;
		if(pnt[now*2].size()&&minz[now*2]<=minz[now*2+1])return find(now*2);
		else return find(now*2+1);
	}
	ll re(ll pos,ll now,ll &frm){//询问指定位置最低点 
//		auto it=pnt[now].find(pos);
//		if(it==pnt[now].end())return N;
		ll mid=(l[now]+r[now])/2,ans=ln[now].find(pos);
		if(l[now]==r[now]){
			frm=ln[now].id;
			return ans;
		}
		push_down(now);
		if(pos<=mid)ans=min(ans,re(pos,now*2,frm));
		else ans=min(ans,re(pos,now*2+1,frm));
		push_up(now);
		return ans;
	}
}LCsgt;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
ll used[MAXN];
struct node_qs{
	ll hd[MAXN*4],nxt[MAXN*4],ed[MAXN*4];
	ll l[MAXN*4],r[MAXN*4],w[MAXN*4],dis[MAXN*4],frm[MAXN];
	ll idx,cnt;
	void build(ll x,ll y){//建边 
		nxt[++idx]=hd[x];
		ed[idx]=y;
		hd[x]=idx;
//		w[idx]=z;
	}
	void insert(ll lz,ll rz,ll wz){//新建区间 
		l[++cnt]=lz,r[cnt]=rz,w[cnt]=wz;
		dis[cnt]=N;
//		return cnt;
	}
	void mk(ll id){//访问区间 
		node_line now;
		now.k=0,now.b=dis[id]+w[id],now.id=frm[id];
//		cout<<"mk: "<<l[id]<<" "<<r[id]<<" "<<now.b<<endl;
		LCsgt.insert(l[id],r[id],1,now);
	}
	void acc(ll id,ll val,ll p){//访问点 
		for(int i=hd[id];i;i=nxt[i]){
			ll y=ed[i];
			if(dis[y]>val){
				dis[y]=val;
				q.push(make_pair(dis[y],y));
				frm[y]=p;
			}
		}
	}
}mp;
struct node_sagment{
	ll l[MAXN*4],r[MAXN*4];
	void build(ll lz,ll rz,ll now){//建树 
		l[now]=lz,r[now]=rz;
		if(lz==rz)return;
		ll mid=(lz+rz)/2;
		build(lz,mid,now*2);
		build(mid+1,rz,now*2+1);
		return;
	}
	void add(ll lz,ll rz,ll now,ll val){//区间建边 
		if(l[now]>=lz&&r[now]<=rz){
			mp.build(now,val);
			return;
		}
		ll mid=(l[now]+r[now])/2;
		if(lz<=mid)add(lz,rz,now*2,val);
		if(rz>mid)add(lz,rz,now*2+1,val);
		return;
	}
	void acc(ll pos,ll now,ll val){//访问出边 
		mp.acc(now,val,pos);
		if(l[now]==r[now])return;
		ll mid=(l[now]+r[now])/2;
		if(pos<=mid)acc(pos,now*2,val);
		else acc(pos,now*2+1,val);
	}
	
}sgt;
vector <ll> vec;
ll n,m,v[MAXN],frm[MAXN];
int main(){
	n=read(),m=read();
	sgt.build(1,n,1);
	LCsgt.build(1,n,1);
//	mp.cnt=n;
	for(int i=1;i<=n;i++){
		v[i]=read();
	}
	for(int i=1;i<=m;i++){
		ll sl=read(),sr=read(),tl=read(),tr=read(),w=read();
		mp.insert(sl,sr,w);
		mp.insert(tl,tr,w);
		sgt.add(tl,tr,1,i*2-1);
		sgt.add(sl,sr,1,i*2);
	}
	LCsgt.insert(1,1,1,(node_line){0,0});
//	debug;
	while(1){
		ll pos=LCsgt.find(1);
		ll val=LCsgt.re(pos,1,frm[pos]);
//		cout<<pos<<" "<<val<<endl;
		ll valq=N;
		while(!q.empty()){
			if(used[q.top().second])q.pop();
			else break;
		}
		if(!q.empty())valq=q.top().first;
		if(val==valq&&val==N){
			cout<<"-1\n";
			return 0;
		}
//		cout<<pos<<" "<<val<<" "<<valq<<endl;
		if(val<valq){
//			cout<<pos<<" "<<val<<" "<<frm[pos]<<endl;
			if(pos==n){
				cout<<val<<endl;
				break;
			}
			LCsgt.del(pos,1);
			sgt.acc(pos,1,val);
			if(!v[pos])continue;
			node_line now;
			if(pos<n){
				now.k=v[pos],now.b=val-v[pos]*pos,now.id=pos;
				LCsgt.insert(pos+1,n,1,now);
			}	
			if(pos>1){
				now.k=-v[pos],now.b=val+v[pos]*pos,now.id=pos;
				LCsgt.insert(1,pos-1,1,now);
			}
		}else{
			used[q.top().second]=1;
			mp.mk(q.top().second);
			q.pop();
		}
	}
	ll now=n;
	while(now){
		vec.push_back(now);
		now=frm[now];
	}
	cout<<vec.size()<<endl;
	for(int i=vec.size()-1;i>=0;i--)cout<<vec[i]<<" ";
	return 0;
}