#pragma GCC optimize "Ofast"
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<ll> point;
#define X real()
#define Y imag()
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const ll INF = 1e17;
const ll sqrtn = 440;
const ll modulo = 1e9+7;
const ll siz = 262144;
const ll hashp = 923981238;
const ll hashm = 932439994;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int ll
struct edge{
int u,v,c,d;
};
edge edgelist[50001];
set<int> adj[201];
int dist[201][201];
int distd[201];
bool visited[201];
int n;
inline int dijkastra(){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
for(int&i:distd)i=INF;
for(bool&i:visited)i=false;
int c1 = INF;
q.emplace(0,1);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
if(curr.second==n){c1=curr.first;break;}
visited[curr.second]=true;
for(auto&i:adj[curr.second])if(distd[edgelist[i].v]>edgelist[i].c+curr.first) {
distd[edgelist[i].v]=edgelist[i].c+curr.first;
q.emplace(edgelist[i].c + curr.first, edgelist[i].v);
}
}
while(!q.empty())q.pop();
for(int&i:distd)i=INF;
for(bool&i:visited)i=false;
int c2 = INF;
q.emplace(0,n);
while(!q.empty()){
auto curr = q.top();q.pop();
if(visited[curr.second])continue;
if(curr.second==1){c2=curr.first;break;}
visited[curr.second]=true;
for(auto&i:adj[curr.second])if(distd[edgelist[i].v]>edgelist[i].c+curr.first) {
distd[edgelist[i].v]=edgelist[i].c+curr.first;
q.emplace(edgelist[i].c + curr.first, edgelist[i].v);
}
}
return c1+c2;
}
void solve() {
int m;
cin >> n >> m;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)dist[i][j]=INF;
for(int i=1;i<=m;i++){
cin >> edgelist[i].u >> edgelist[i].v >> edgelist[i].c >> edgelist[i].d;
adj[edgelist[i].u].insert(i);
dist[edgelist[i].u][edgelist[i].v] = min(dist[edgelist[i].u][edgelist[i].v],edgelist[i].c);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
int ans = dist[1][n]+dist[n][1];
for(int i=1;i<=m;i++){
auto curr = edgelist[i];
if(min(dist[1][n],dist[1][curr.v]+dist[curr.u][n]+curr.c)+min(dist[n][1],dist[n][curr.v]+dist[curr.u][1]+curr.c)+curr.d<ans){
adj[curr.u].erase(i);
adj[curr.v].insert(i);
swap(edgelist[i].u,edgelist[i].v);
ans = min(ans,dijkastra()+curr.d);
adj[curr.v].erase(i);
adj[curr.u].insert(i);
swap(edgelist[i].u,edgelist[i].v);
}
}
cout << (ans>=INF ? -1 : ans)<< '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("mock.txt","r",stdin);
// freopen(".out","w",stdout);
// int t;
// cin >> t;
// while(t--)
solve();
}
