玄关

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){
	int w=0;x=0;
	char ch = getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
template <typename T>
inline T Min(T x,T y){ return (x < y ? x : y); }
template <typename T>
inline T Max(T x,T y){ return (x > y ? x : y); }
const int N = 1e5+10,LG = 17;
int n,m; ll INF;
struct{
	int to,nex; ll w;
}edge[N*LG];
int head[N*LG],edge_num;
inline void add(int x,int y,ll w){
	edge[++edge_num].to = y;
	edge[edge_num].nex = head[x];
	head[x] = edge_num;
	edge[edge_num].w = w;
}
int P=1,DEP=0,NOW;
inline void update(int v,int l,int r){
	l += P-1; r += P+1;
	while(l^1^r){
		if(~l&1) add(l^1,v,0);
		if(r&1) add(r^1,v,0);
		l>>=1;r>>=1;
	}
}
struct node{
	ll w; int p;
	bool operator < (const node&G) const{
		return w > G.w;
	}
};
ll dis[N*6],tmp[N*6];bool vis[N*6];
priority_queue <node> q;
inline void dijs(){
	memset(vis,false,sizeof(vis));
	while(!q.empty()){
		node now = q.top();
		q.pop();
		if(vis[now.p]) continue;
		vis[now.p] = 1;
		for(int i=head[now.p];i;i=edge[i].nex){
			int tto = edge[i].to;
			if(dis[tto]>dis[now.p]+edge[i].w){
				dis[tto] = dis[now.p]+edge[i].w;
				if(!vis[tto]) q.push({dis[tto],tto});
			}
		}
	}
}
int main(){
// 	freopen("in.in","r",stdin);
// 	freopen("out.out","w",stdout);
	
	read(n,m);
	while(P<=n+1) P<<=1,++DEP;
	NOW = (1<<(DEP+1))-1;
	// cout << P << " " << DEP << " " << NOW << endl;
	for(int i=P-1;i;--i) add(i<<1,i,0),add(i<<1|1,i,0);
	for(int i=1,v,k,l,r;i<=m;++i){
		read(v,k,l,r);
		add(++NOW,v+P,1ll*k);
		update(NOW,l,r);
	}

	memset(dis,0x3f,sizeof(dis));
	INF = dis[1]; dis[1+P] = 0;
	q.push({0,P+1}); dijs();
	for(int i=1;i<=NOW;++i) tmp[i] = dis[i];

	memset(dis,0x3f,sizeof(dis));
	INF = dis[1]; dis[n+P] = 0;
	q.push({0,P+n}); dijs();

	for(int i=1;i<=NOW;++i){
		dis[i] += tmp[i];
		q.push({(dis[i],i)});
	}
	dijs();
	for(int i=1;i<=n;++i) printf("%lld\n",dis[i+P]>=INF?-1:dis[i+P]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}