Dij80pts求调qwq

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1005],b[1005],c[1005],gg,INF=1e16,dp[1005],vis[1005],ans,zd;
vector< pair<long long,long long> > vec[1005];
priority_queue< pair<long long,long long> > q;
inline void Dij(){
	q.push({0,1});
	while(!q.empty()){
		long long f=q.top().second;
		q.pop();
		if(vis[f]) continue;
		vis[f]=1;
		for(int i=0;i<vec[f].size();i++){
			long long w=vec[f][i].first,to=vec[f][i].second;
			if(dp[f]+w<dp[to]){
				dp[to]=dp[f]+w;
				q.push({-w,to});
			}
		}
	}
}
inline void write(long long x){
	if(x==INF) cout<<-1;
	else cout<<x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
		if(a[i]==1&&b[i]==1) gg=i;
		if(a[i]==m&&b[i]==m) zd=i;
	}
	for(int i=1;i<=1002;i++) dp[i]=INF;
	dp[gg]=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]==a[j]&&abs(b[i]-b[j])<=1){
				vec[i].push_back({abs(c[i]-c[j]),j});
				vec[j].push_back({abs(c[i]-c[j]),i});
			}
			else if(b[i]==b[j]&&abs(a[i]-a[j])<=1){
				vec[i].push_back({abs(c[i]-c[j]),j});
				vec[j].push_back({abs(c[i]-c[j]),i});
			}
			else if(abs(a[i]-a[j])+abs(b[i]-b[j])==2){
				vec[i].push_back({abs(c[i]-c[j])+2,j});
				vec[j].push_back({abs(c[i]-c[j])+2,i});
			}
		}
	}
	Dij();
	ans=INF;
	if(zd!=0) write(dp[zd]);
	else{
		for(int i=1;i<=n;i++){
			if((a[i]==m&&b[i]==m-1)||(a[i]==m-1&&b[i]==m)){
				ans=min(ans,dp[i]+2);
			}
		}
		write(ans);
	}
}