#include <iostream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

struct wear{
    int a,b,c;
};

vector<vector<int> > memovul;
int n;

int vest(const int* tmp,const wear* wd,const int d);

int main()
{
	int d;
	cin>>d>>n;
	//table.resize(n,vector<int>(n,-1));
	memovul.resize(d);
	for(int i=0;i<d;i++){
		memovul[i].resize(n,-1);
	}
	int* temperature=new int[d];
	wear* wearsdata=new wear[n];
	for(int i=d-1;i>=0;i--){
		cin>>temperature[i];
	}
	for(int i=0;i<n;i++){
		cin>>wearsdata[i].a>>wearsdata[i].b>>wearsdata[i].c;
	}
	cout<<vest(temperature,wearsdata,d)<<endl;
}
int vest(const int* tmp,const wear* wd,const int d)
{
	pair<int,int> table[2][2]={pair<int,int>(-1,0),pair<int,int>(-1,0),pair<int,int>(-1,0),pair<int,int>(-1,0)};
	int dabs;
	for(int i=0;i<d;i++){
		table[i%2][0].first=-1;
		for(int j=0;j<n;j++){
			if(wd[j].a<=tmp[i] && wd[j].b>=tmp[i]){
				if(table[i%2][0].first==-1){
					table[i%2][0].first=j;
					table[i%2][1].first=j;
					if(i){
						dabs=abs(wd[table[(i+1)%2][0].first].c-wd[j].c)+table[(i+1)%2][0].second;
						table[i%2][0].second=abs(wd[table[(i+1)%2][1].first].c-wd[j].c)+table[(i+1)%2][1].second;
						if(dabs>table[i%2][0].second){
							table[i%2][0].second=dabs;
						}
						table[i%2][1].second=table[i%2][0].second;
					}
				}else{
					if(wd[table[i%2][0].first].c<wd[j].c){
						if(i){
							dabs=abs(wd[table[(i+1)%2][0].first].c-wd[j].c)+table[(i+1)%2][0].second;
							table[i%2][0].second=abs(wd[table[(i+1)%2][1].first].c-wd[j].c)+table[(i+1)%2][1].second;
							if(dabs>table[i%2][0].second){
								table[i%2][0].second=dabs;
							}
						}
						table[i%2][0].first=j;
					}else if(wd[table[i%2][1].first].c>wd[j].c){
						if(i){
							dabs=abs(wd[table[(i+1)%2][1].first].c-wd[j].c)+table[(i+1)%2][1].second;
							table[i%2][1].second=abs(wd[table[(i+1)%2][0].first].c-wd[j].c)+table[(i+1)%2][0].second;
							if(dabs>table[i%2][1].second){
								table[i%2][1].second=dabs;
							}
						}
						table[i%2][1].first=j;
					}
				}
			}
		}
	}
	if(table[(d+1)%2][0].second<table[(d+1)%2][1].second){
		return table[(d+1)%2][1].second;
	}
	return table[(d-1)%2][0].second;
}