#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
vector<vector<pair<ll,ll>>> cad;
vector<map<ll,ll>> c1,c2;
vector<pair<ll,ll>> E;
struct st{
ll cost,node,ed;
friend bool operator < (st a, st b)
{
return a.cost<b.cost;
}
};
ll cmc()
{
vector<unordered_map<ll,ll>> v(cad.size());
for(int i=1; i<cad.size(); i++){
v[i][E.size()-1]=1e16;
for(int j=0; j<cad[i].size(); j++)
v[i][cad[i][j].y]=1e16;}
priority_queue<st>q;q.push({0,1,(ll)E.size()-1});
while(!q.empty())
{
st temp=q.top();q.pop();
//cerr<<temp.node<<" "<<temp.cost<<"\n";
if(v[temp.node][temp.ed]==1e16)
{
if(temp.node==cad.size()-1) return -temp.cost;
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;
q.push({temp.cost-cnt,i.x,(ll)E.size()-1});
q.push({temp.cost-E[i.y].y,i.x,i.y});
}
}
}
return 1e16;
}
int main()
{
ll n,m;
cin>>n>>m;
cad.resize(n+1);
c1.resize(n+1);
c2.resize(n+1);
E.resize(m+2);
for(int i=0; i<m; i++)
{
ll a,b;
cin>>a>>b>>E[i].x>>E[i].y;
cad[a].push_back({b,i});
cad[b].push_back({a,i});
c1[a][E[i].x]++;
c2[a][E[i].x]+=E[i].y;
c1[b][E[i].x]++;
c2[b][E[i].x]+=E[i].y;
}
ll t1=cmc();
if(t1==1e16) t1=-1;
cout<<t1;
}
/*
13 21
7 10 4
3 6 4
8 10 4
3 9 2
1 4 4
2 6 4
3 11 2
3 8 16
8 11 16
6 10 4
6 8 16
9 12 16
5 13 4
1 12 4
2 4 4
2 9 4
2 12 4
10 13 4
5 7 2
5 11 2
7 13 4
13 21
1 4 4 5
2 4 4 18
1 12 4 7
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
*/
