#include<bits/stdc++.h>
#define int long long
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin >> n >> m;
vector<array<int,2>> a[n+1];
m/=2;
while(m--)
{
int u,v,c,d;
cin >> u >> v >> c >> d;
int cu,cv,cc,cd;
cin >> cu >> cv >> cc >> cd;
a[u].push_back({v,c});
a[v].push_back({u,c+min(cd,d)});
}
vector<int> dist(n+1,1e18);
dist[1] = 0;
priority_queue<array<int,2>> pq;
pq.push({0,1});
while(pq.size())
{
int s = pq.top()[1];
pq.pop();
for(auto &[x,w]:a[s])
{
if(dist[x]>dist[s]+w)
{
dist[x] = dist[s]+w;
pq.push({-dist[x],x});
}
}
}
int sum = dist[n];
dist = vector<int>(n+1,1e18);
dist[n] = 0;
pq.push({0,n});
while(pq.size())
{
int s = pq.top()[1];
pq.pop();
for(auto &[x,w]:a[s])
{
if(dist[x]>dist[s]+w)
{
dist[x] = dist[s]+w;
pq.push({-dist[x],x});
}
}
}
sum+=dist[1];
if(sum>=1e18)
{
cout << -1 << endl;
}
else
cout << sum << endl;
}
