#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
struct Edge{
int u, v, c, d;
Edge(){};
};
const int MAX_E = 5*1e4;
const int MAX_V = 200;
const int INF = 1e18;
int v, e;
Edge edges[MAX_E];
vector<pii> adj[MAX_V];
vector<int> find_path(int begin, int dest){
vector<int> dist(v, INF);
vector<pii> prev(v, pii(-1, -1));
dist[begin] = 0;
priority_queue<pii> pq;
pq.push(pii(0, begin));
while(pq.size()>0){
auto cur = pq.top();
pq.pop();
int u = cur.second;
int u_dist = -cur.first;
if(dist[u] == u_dist){
//cout<<u<<" "<<dist[u]<<endl;
for(auto next: adj[u]){
int next_dist = u_dist + edges[next.second].c;
if(next_dist< dist[next.first]){
dist[next.first] = next_dist;
pq.push(pii(-next_dist, next.first));
prev[next.first].first = u;
prev[next.first].second = next.second;
}
}
}
}
if(dist[dest] == INF){
return vector<int>(0);
}
else{
int cur = dest;
vector<int> res;
while(cur!=begin){
res.push_back(prev[cur].second);
cur = prev[cur].first;
}
return res;
}
}
int d[MAX_V][MAX_V];
bool is_path[MAX_E];
void find_d(){
for(int i = 0; i<MAX_V; i++){
for(int j = 0; j<MAX_V; j++){
d[i][j] = INF;
}
}
for(int i = 0; i<v; i++){
d[i][i] = 0;
}
for(int i = 0; i<e; i++){
if(edges[i].u!=-1){
d[edges[i].u][edges[i].v] = min(d[edges[i].u][edges[i].v], edges[i].c);
}
}
}
void floyd(){
for(int mid= 0; mid<v; mid++){
for(int f= 0; f<v; f++){
for(int l = 0; l<v; l++){
d[f][l] = min(d[f][l], d[f][mid] + d[mid][l]);
}
}
}
}
signed main(){
cin>>v>>e;
for(int i = 0; i<e; i++){
cin>>edges[i].u>>edges[i].v>>edges[i].c>>edges[i].d;
edges[i].u--;
edges[i].v--;
adj[edges[i].u].push_back(pii(edges[i].v, i));
//d[edges[i].u][edges[i].v] = min(d[edges[i].u][edges[i].v], edges[i].c);
}
auto p1 = find_path(0, v-1);
auto p2 = find_path(v-1, 0);
for(auto e: p1){
is_path[e] = true;
}
for(auto e: p2){
is_path[e] = true;
}
find_d();
floyd();
int go = d[0][v-1];
int back = d[v-1][0];
int res= go +back;
//cout<<go<<" "<<back<<endl;
for(int i = 0; i<e; i++){
if(!is_path[i]){
int from = edges[i].v;
int to = edges[i].u;
int cost = edges[i].c + edges[i].d;
res = min(res, min(go + d[v-1][from] + d[to][0], back + d[0][from] + d[to][v-1]) + cost);
}
}
for(int i = 0; i<e; i++){
if(is_path[i]){
int origin = edges[i].u;
edges[i].u = -1;
find_d();
floyd();
edges[i].u = origin;
int from = edges[i].v;
int to = edges[i].u;
int cost = edges[i].c + edges[i].d;
res = min(res, min(d[0][v-1] + d[v-1][from] + d[to][0], d[v-1][0]+ d[0][from] + d[to][v-1]) + cost);
}
}
if(res>=INF){
cout<<-1<<endl;
return 0;
}
cout<<res<<endl;
}
