有几个点没过，record。

每个点好像都要比答案大一点，实在是调不出来了qwq

#include<bits/stdc++.h>
using namespace std;
const int maxn=220;
const int maxm=5e4+5;
const long long INF=1e13;
#define ll long long
struct node{
	ll from,next,to,w,d;
}e[maxm];
ll n,m,head[maxn],idx,vis[maxn],dis_init[maxn][maxn],dis[maxn],pre[maxn],rec1[maxm],rec2[maxm],ans;
inline void add(ll u,ll v,ll w,ll d){
	e[++idx].to=v,e[idx].from=u,e[idx].next=head[u],e[idx].w=w,e[idx].d=d,head[u]=idx;
}
inline void dijkstra_rec(ll s){
	for(int i=0;i<=n;i++) dis[i]=INF,vis[i]=pre[i]=0;
	dis[s]=0;
	while(true){
		ll u=0;
		for(int i=1;i<=n;i++) if(dis[u]>dis[i]&&!vis[i]) u=i;
		if(!u) break;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next){
			ll v=e[i].to;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				pre[v]=i;
			}
		}
	}
}
inline void dijkstra_count(ll s){
	for(int i=0;i<=n;i++) dis[i]=INF,vis[i]=0;
	dis[s]=0;
	while(true){
		ll u=0;
		for(int i=1;i<=n;i++) if(dis[u]>dis[i]&&!vis[i]) u=i;
		if(!u) break;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next){
			ll v=e[i].to;
			dis[v]=min(dis[v],dis[u]+e[i].w);
		}
	}
}
inline void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis_init[i][j]=min(dis_init[i][k]+dis_init[k][j],dis_init[i][j]);
			}
		}
	}
}
inline void solve(){
	dijkstra_rec(1);
	ll now=n,cnt=INF,res;
	while(now){
		rec1[pre[now]]=1;
		now=e[pre[now]].from;
	}
	now=1;
	dijkstra_rec(n);
	while(now){
		rec2[pre[now]]=1;
		now=e[pre[now]].from;
	}
	ans=dis_init[1][n]+dis_init[n][1];
	
	for(int i=1;i<=m;i++){
		if(rec1[i]){
			swap(e[i].from,e[i].to);
			dijkstra_count(1);
			res=dis[n];
			swap(e[i].from,e[i].to);
		}
		else res=min(dis_init[1][n],dis_init[1][e[i].to]+e[i].d+e[i].w+dis_init[e[i].from][n]);
		if(rec2[i]){
			swap(e[i].from,e[i].to);
			dijkstra_count(n);
			res+=dis[1];
			swap(e[i].from,e[i].to);
		}
		else res+=min(dis_init[n][1],dis_init[n][e[i].to]+e[i].d+e[i].w+dis_init[e[i].from][1]);
		ans=min(ans,res);
	}
}

int main(){
	ll u,v,w,d;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis_init[i][j]=INF;
			if(i==j) dis_init[i][j]=0;
		} 
	} 
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld%lld",&u,&v,&w,&d);
		add(u,v,w,d),dis_init[u][v]=min(dis_init[u][v],w);
	}
	floyd();
	solve();
	printf("%lld\n",ans>=INF?-1:ans);
	return 0;
}