#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} int readint(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt[100005]; vector<array<int,3>> g[100005]; map<pii,int> dist; int main(){ n=readint(); m=readint(); for(int i=1;i<=m;i++){ int u=readint(),v=readint(),c=readint(),p=readint(); g[u].pb({v,c,0}); g[v].pb({u,c,0}); if(m!=1){ g[u].pb({v,(c==m?1:c+1),p}); g[v].pb({u,(c==m?1:c+1),p}); g[u].pb({v,(c==1?m:c-1),p}); g[v].pb({u,(c==1?m:c-1),p}); } } set<tuple<ll,int,int>> st; dist[mp(1,1)]=0; st.emplace(0ll,1,1); if(m!=1){ dist[mp(1,2)]=0; st.emplace(0ll,1,2); } while(!st.empty()){ auto it=st.begin(); ll d=get<0>(*it); int x=get<1>(*it); int c=get<2>(*it); st.erase(it); cnt[x]++; if(x==n){ printf("%lld\n",d); exit(0); } if(cnt[x]>2) continue; for(auto&p:g[x]){ int to=get<0>(p); int col=get<1>(p); int w=get<2>(p); if(c==col) continue; if(!dist.count(mp(to,col))||dist[mp(to,col)]>d+w){ if(dist.count(mp(to,col))) st.erase(st.find({dist[mp(to,col)],to,col})); dist[mp(to,col)]=d+w; st.emplace(dist[mp(to,col)],to,col); } } } printf("-1\n"); return 0; }