#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=4e5+5;

struct Node{
    int e,t,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,int> csum[N],ccnt[N];
int dis[N][2],vis[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;
    ccnt[x][z]++;
}

signed main()
{
    cin>>n>>m;
    
    tot=1;
    For(i,1,m){
        int x,y,z,w;
        cin>>x>>y>>z>>w;
        add(x,y,z,w);
        add(y,x,z,w);
    }
    
    clr(dis,0x3f);
    
    for(int e=head[1];e;e=nxt[e]){
        int 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]});
    }
    
    int ans=dis[0][0];
    
    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=min(ans,dis[e0][t]);
        
        for(int e=head[u];e;e=nxt[e]){
            if(e==(e0^1)) continue;
            
            int cost=csum[u][col[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]});
            }
        }
    }
    
    if(ans<dis[0][0]) cout<<ans<<endl;
    else cout<<-1<<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
*/