#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iiii tuple<int, int,int,int>
#define ld long double
#define lol pair<pll,pll>
#define iii tuple<int,int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int n,m;
vector<vector<iii>> al(205), tal(205);
vector<tuple<int,int,int,int>> ed;
vector<int> dijk(int s, int skip, vector<vector<iii>> & aa){
vector<int> dist(n+1, 1e15);
dist[s]=0;
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0, s});
while(!pq.empty()){
auto [d,c]=pq.top();pq.pop();
if(dist[c]<d)continue;
for(auto [to,w,ind]:aa[c]){
if(dist[to]<d+w or ind==skip)continue;
dist[to]=d+w;
pq.push({dist[to],to});
}
}
return dist;
}
signed main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c,d;cin>>a>>b>>c>>d;
ed.pb({a,b,c,d});
al[a].pb({b,c,i});
tal[b].pb({a,c,i});
}
vector<int> an, at, bn, bt;
int ans=1e15;
an=dijk(1, m, al), bn=dijk(n, m, al);
ans=min(ans, an[n]+bn[1]);
for(int i=0;i<m;i++){
auto [a,b,c,d]=ed[i]; // a --> b
an=dijk(1, i, al), bn=dijk(n, i, al), at=dijk(1, i, tal), bt=dijk(n, i, tal);
// use on forward trip
ans=min(ans, an[b]+c+d+bt[a]+bn[1]);
// use on backwards trip
ans=min(ans, an[n]+bn[b]+c+d+at[a]);
}
cout<<(ans > 1e14? -1 : ans);
}
