#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;
}
