先反建边刷两套GPS的最短路，再重新建边按照每套导航走每条路骂人的次数刷最短路。
利用手写堆来优化DIJ。 WA on #5~#10

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005,maxe=50005;
int n,m,lnk_GPS[2][maxn],tot,lnk[maxn],dis_GPS[2][maxn],dis[maxn],hep_size;
bool vis[maxn];
struct edge{
	int to,nxt,w;
}e_GPS[2][maxe],e[maxe];
struct BNS{
	int x,id;
	bool operator<(const BNS &B)const{return x<B.x;}
}hep[maxn];
struct ZYX{
	int A,B,P,Q;
}a[maxe];
int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f^=!(ch^'-'),ch=getchar(); 
	while( isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
	return f?ret:-ret;
}
void Add_e(int p,int x,int y,int z){e_GPS[p][++tot]=(edge){y,lnk_GPS[p][x],z},lnk_GPS[p][x]=tot;}
void add_e(int x,int y,int z){e[++tot]=(edge){y,lnk[x],z},lnk[x]=tot;}
void put(int x,int id){
	hep[++hep_size]=(BNS){x,id};int son=hep_size;
	while(son>1&&hep[son]<hep[son>>1]) swap(hep[son],hep[son>>1]),son>>=1;
}
BNS get(){
	BNS now=hep[1];int fa=1,son;hep[1]=hep[hep_size--];
	while((fa<<1)<=hep_size){
		if((fa<<1|1)>hep_size||hep[fa<<1]<hep[fa<<1|1]) son=fa<<1;else son=fa<<1|1;
		if(hep[fa]<hep[son]) swap(hep[fa],hep[son]),fa=son;else break;
	}return now;
}
void DIJ_HEAP_GPS(int p,int sx,int sy){
	memset(dis_GPS[p],63,sizeof dis_GPS[p]),memset(vis,0,sizeof vis);
	memset(hep,0,sizeof hep),hep_size=0;
	put(dis_GPS[p][sx]=0,sx);
	while(hep_size){
		BNS now=get();
		if(vis[now.id]) continue;vis[now.id]=1;
		for(int j=lnk_GPS[p][now.id];j;j=e_GPS[p][j].nxt)
		  if(dis_GPS[p][now.id]+e_GPS[p][j].w<dis_GPS[p][e_GPS[p][j].to]) put(dis_GPS[p][e_GPS[p][j].to]=dis_GPS[p][now.id]+e_GPS[p][j].w,e_GPS[p][j].to);
	}return ;
}
void DIJ_HEAP(){
	memset(dis,63,sizeof dis),memset(vis,0,sizeof vis);
	memset(hep,0,sizeof hep),hep_size=0;
	put(dis[1]=0,1);
	while(hep_size){
		BNS now=get();
		if(vis[now.id]) continue;vis[now.id]=1;
		for(int j=lnk[now.id];j;j=e[j].nxt)
		  if(dis[now.id]+e[j].w<dis[e[j].to]) put(dis[e[j].to]=dis[now.id]+e[j].w,e[j].to);
	}return ;
}
int main(){
	freopen("gpsduel.in","r",stdin);
	freopen("gpsduel.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		a[i].A=read(),a[i].B=read(),a[i].P=read(),a[i].Q=read();
		Add_e(0,a[i].B,a[i].A,a[i].P),Add_e(1,a[i].B,a[i].A,a[i].Q);
	}DIJ_HEAP_GPS(0,n,1),DIJ_HEAP_GPS(1,n,1),tot=0;
	for(int i=1;i<=m;i++){
		int flg1=1,flg2=1;
		if(dis_GPS[0][a[i].B]+a[i].P==dis_GPS[0][a[i].A]) flg1=0;
		if(dis_GPS[1][a[i].B]+a[i].Q==dis_GPS[1][a[i].A]) flg2=0;
		add_e(a[i].A,a[i].B,flg1+flg2);
	}DIJ_HEAP();
	printf("%d\n",dis[n]);
	return 0;
}