#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const int mxn = 202;
const int mxn2 = 5e4+10;
const ll inf = 1e18;
ll dist[mxn];
struct edge{
ll from,to,val,id,cost;
edge(){}
edge(ll ff,ll tt,ll vv,ll cc,ll ii){
from = ff,to = tt,val = vv,cost = cc;
id = ii;
}
};
vector<edge> paths[mxn];
edge edges[mxn2];
int n,m;
ll dijkstra(int s,int no){
priority_queue<pll,vector<pll>,greater<pll>> pq;
fill(dist,dist+mxn,inf);
dist[s] = 0;
pq.push({0,s});
while(!pq.empty()){
auto now = pq.top();
pq.pop();
if(now.fs != dist[now.sc])continue;
for(auto &nxt:paths[now.sc]){
if(nxt.id == no)continue;
if(nxt.val+dist[now.sc]<dist[nxt.to]){
dist[nxt.to] = nxt.val+dist[now.sc];
pq.push({dist[nxt.to],nxt.to});
}
}
}
if(s == 1)return dist[n];
else return dist[1];
}
void solve(){
cin>>n>>m;
ll ans = inf;
if(m>1000){
for(int i = 2;i<=m;i+=2){
ll c;
edges[i].id = i>>1;
cin>>edges[i].from>>edges[i].to>>edges[i].val>>edges[i].cost;
cin>>c>>c>>c>>c;
edges[i].cost = min(edges[i].cost,c);
paths[edges[i].from].push_back(edges[i]);
}
}
else{
for(int i = 1;i<=m;i++){
ll c;
edges[i].id = i>>1;
cin>>edges[i].from>>edges[i].to>>edges[i].val>>edges[i].cost;
paths[edges[i].from].push_back(edges[i]);
}
}
ans = dijkstra(1,0)+dijkstra(n,0);
for(int i = 1;i<=m;i++){
paths[edges[i].to].push_back(edge(edges[i].to,edges[i].from,edges[i].val,edges[i].cost,-edges[i].id));
ll tmp = edges[i].cost+dijkstra(1,i)+dijkstra(n,i);
ans = min(ans,tmp);
paths[edges[i].to].pop_back();
}
cout<<(ans>=inf?-1:ans)<<'\n';
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while(t--)solve();
}
