#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef long long ll;
#define x first
#define y second
vector<vector<pair<int,int>>> cad;
map<int,vector<pair<int,int>>> cad2[(ll)1e5+5];
vector<map<int,ll>> c2;
vector<pair<int,int>> E;
int n,m;
struct st{
ll cost;int node,ed;
friend bool operator < (st a, st b)
{
return a.cost>b.cost;
}
};
ll cmc()
{
vector<map<int,ll>> v(cad.size()),v2(cad.size());
priority_queue<st>q;q.push({1,1,m+1});
while(!q.empty())
{
st temp=q.top();q.pop();
//cerr<<temp.node<<" "<<temp.cost-1<<"\n";
if(temp.ed==m+1)
{
if(v[temp.node][temp.ed]==0)
{
if(temp.node==n) return temp.cost-1;
v[temp.node][temp.ed]=temp.cost;
for(auto i:cad[temp.node])
{
ll cnt=c2[temp.node][E[i.y].x]-E[i.y].y;
if(E[temp.ed].x==E[i.y].x)
cnt-=E[temp.ed].y;
ll t1=v2[i.x][m+1];
if(t1==0||temp.cost+min(cnt,(ll)E[i.y].y)<t1)
{
q.push({temp.cost+min(cnt,(ll)E[i.y].y),i.x,m+1});
}
t1=v2[i.x][i.y];
if(t1==0||temp.cost+E[i.y].y<t1)
{
q.push({temp.cost+E[i.y].y,i.x,i.y});
}
}
}
}
else if(v[temp.node][temp.ed]==0)
{
if(temp.node==n) return temp.cost-1;
v[temp.node][temp.ed]=temp.cost;
for(auto i:cad2[temp.node][E[temp.ed].x])
{
ll cnt=c2[temp.node][E[i.y].x]-E[i.y].y;
if(E[temp.ed].x==E[i.y].x)
cnt-=E[temp.ed].y;
ll t1=v2[i.x][m+1];
if(t1==0||temp.cost+min(cnt,(ll)E[i.y].y)<t1)
{
q.push({temp.cost+min(cnt,(ll)E[i.y].y),i.x,m+1});
}
t1=v2[i.x][i.y];
if(t1==0||temp.cost+E[i.y].y<t1)
{
q.push({temp.cost+E[i.y].y,i.x,i.y});
}
}
}
}
return 1e16;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
cad.resize(n+1);
c2.resize(n+1);
E.resize(m+2);
for(int i=0; i<m; i++)
{
int a,b;
cin>>a>>b>>E[i].x>>E[i].y;
cad[a].push_back({b,i});
cad[b].push_back({a,i});
c2[a][E[i].x]+=E[i].y;
c2[b][E[i].x]+=E[i].y;
cad2[a][E[i].x].push_back({b,i});
cad2[b][E[i].x].push_back({a,i});
}
ll t1=cmc();
if(t1==1e16) t1=-1;
cout<<t1;
}
