本人本地实测，#2数据能跑出来答案（只是花了31秒而已）

#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,w[2];
};
struct edge{
	int s,t,cnt=2;
}e[50005];
vector<node>a[10005],b[10005];
int dist[10005],last[2][10005],n,m;
bool flag[10005];
map<pair<int,int>,int>mp1;
map<pair<int,int>,bool>mp2[2];
void find_path(int s,int p,int l){
	if(last[l][p]==s||last[l][p]==0){
		if(!mp2[l][{last[l][p],p}]){
			mp1[{last[l][p],p}]++;
			mp2[l][{last[l][p],p}]=true;
		}
		return;
	}
	find_path(s,last[l][p],l);
	if(!mp2[l][{last[l][p],p}]){
		mp1[{last[l][p],p}]++;
		mp2[l][{last[l][p],p}]=true;
	}
	return;
	
}
void dij(int s,int l){
	priority_queue<pair<int,int> >q;
	memset(dist,0x3f,sizeof dist);
	memset(flag,false,sizeof flag);
	dist[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int tot=q.top().second;
		q.pop();
		if(flag[tot])continue;
		flag[tot]=1;
		for(int i=0;i<a[tot].size();i++){
			int t=a[tot][i].to;
			if(dist[t]>dist[tot]+a[tot][i].w[l]){
				dist[t]=dist[tot]+a[tot][i].w[l];
				q.push({-dist[t],t});
				last[l][t]=tot;
			}
		}
	}
	for(int i=1;i<=n;i++)if(i!=s)find_path(s,i,l);
}
int main(){
	freopen("P3106_2.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int re,er,c,d;
		cin>>re>>er>>c>>d;
		node p;
		p.to=re;
		p.w[0]=c;
		p.w[1]=d;
		a[er].push_back(p);
		e[i].s=er;
		e[i].t=re;
	}
//	for(int i=1;i<=n;i++){
//		cout<<endl<<i<<':'<<'\t';
//		for(int j=0;j<a[i].size();j++){
//			cout<<a[i][j].to<<' '<<a[i][j].w[0]<<' '<<a[i][j].w[1]<<'\t';
//		}
//	}
	dij(n,0);
//	cout<<endl;
//	for(int i=1;i<=n;i++)cout<<dist[i]<<' ';
//	cout<<endl;
	dij(n,1);
//	for(int i=1;i<=n;i++)cout<<dist[i]<<' ';
//	cout<<endl;
	for(int i=1;i<=n;i++)a[i].clear();
	for(int i=1;i<=m;i++){
		e[i].cnt-=mp1[{e[i].s,e[i].t}];
	//	cout<<e[i].s<<' '<<e[i].t<<' '<<e[i].cnt<<'\t';
		node p;
		p.to=e[i].t;
		p.w[0]=e[i].cnt;
		a[e[i].s].push_back(p);
	}
	dij(n,0);
	//cout<<endl;
	cout<<dist[1];
	return 0;
}

注释中是调试代码。。。