分层图求调……

#include<cstdio>
#include<queue>
using namespace std;
inline int in(){
	int x=0,f=1;char c;
	c=getchar();
	while (c<'0'||c>'9'){
		if (c=='-')f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
struct edge{int to,nex,dis;}w[4000001];
int head[4000001],id,n,m,dis[4000001];
bool vis[4000001];
inline void add(int u,int v,int d){
    w[++id].dis=d;
   	w[id].to=v;
    w[id].nex=head[u];
    head[u]=id;
}
struct node{
    long long dis;int pos;
    bool operator<(const node &x)const{return x.dis<dis;}
};
priority_queue<node> q;
inline void dijkstra(){
    for (int i=3*n;i>=1;i--)dis[i]=1e9;
    dis[1]=0;q.push({0,1});
    while(!q.empty()){
        int x=q.top().pos;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for (int i=head[x];i;i=w[i].nex){
            int y=w[i].to;
            if(dis[y]>dis[x]+w[i].dis){
            	dis[y]=dis[x]+w[i].dis;
                q.push({dis[y],y});
            }
        }
    }
}
int main(){
    n=in(),m=in();
    while (m--){
    	int u=in(),v=in(),d=in(),w=in();
        if (w==1){
			add(u,v+n,d);add(v,u+n,d);
			add(u+n,v+n+n,d);add(v+n,u+n+n,d);
		}
		else {
			add(u,v,d);add(v,u,d);
			add(u+n,v+n,d);add(v+n,u+n,d);
			add(u+n,v+n+n,d);add(v+n,u+n+n,d);
		}
    }
    dijkstra();
    printf ("%d",dis[n]-min(dis[n],min(dis[n+n],dis[n+n+n])));
    return 0;
}