#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Fin(file) freopen(file".in","r",stdin)
#define Fout(file) freopen(file".out","w",stdout)
#define Fgen(file) freopen(file".in","w",stdout)
#define Fans(file) freopen(file".ans","w",stdout)
// #define int long long
using namespace std;

const int N=1e6+5;
typedef long long ll;

struct Node{
    int e,t;
    ll d;
    bool operator< (const Node& nd) const
    {
        return d>nd.d;
    }
};

int n,m,head[N],nxt[N],to[N],col[N],cst[N],tot;
unordered_map<int,ll> csum[N];
ll sum[N];
int vis[N][2];
ll dis[N][2];
priority_queue<Node> q;

void add(int x,int y,int z,int w)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    col[tot]=z;
    cst[tot]=w;
    csum[x][z]+=w;
}

int read()
{
    char Charlie;
    while((Charlie=getchar())<'0'||Charlie>'9') ;
    int Vinnie=Charlie-'0';
    while((Charlie=getchar())>='0'&&Charlie<='9') Vinnie=(Vinnie<<3)+(Vinnie<<1)+Charlie-'0';
    return Vinnie;
}

signed main()
{
    Fin("L");
    n=read(); m=read();
    
    tot=1;
    For(i,1,m){
        int x,y,z,w;
        x=read(); y=read(); z=read(); w=read();
        add(x,y,z,w);
        add(y,x,z,w);
    }
    
    For(e,2,tot){
        sum[e]=csum[to[e^1]][col[e]];
    }
    
    clr(dis,0x3f);
    
    for(int e=head[1];e;e=nxt[e]){
        ll cost=csum[1][col[e]]-cst[e];
        dis[e][0]=cost;
        q.push({e,0,cost});
        dis[e][1]=cst[e];
        q.push({e,1,cst[e]});
    }
    
    ll ans=-1;
    
    while(q.size()){
        int e0=q.top().e,t=q.top().t; q.pop();
        if(vis[e0][t]) continue;
        vis[e0][t]=1;
        
        int u=to[e0];
        
        if(u==n){
            ans=dis[e0][t];
            break;
        }
        
        for(int e=head[u];e;e=nxt[e]){
            if(e==(e0^1)) continue;
            
            ll cost=sum[e]-cst[e];
            if(col[e]==col[e0] && t) cost-=cst[e0];
            assert(cost>=0);
            
            if(!vis[e][0] && dis[e][0]>dis[e0][t]+cost){
                dis[e][0]=dis[e0][t]+cost;
                q.push({e,0,dis[e][0]});
            }
            
            
            if(!vis[e][1] && dis[e][1]>dis[e0][t]+cst[e]){
                dis[e][1]=dis[e0][t]+cst[e];
                q.push({e,1,dis[e][1]});
            }
        }
    }
    
    cout<<ans<<endl;
    
    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/