#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> i4;
i4 G[50005];
vector<ii> adjlist[205];
int ans = 2000000000;
int n,m;
int dist[205];
priority_queue<ii,vector<ii>, greater<ii> > pq;
int test(){
for (int i = 1; i <= n; i++) adjlist[i].clear();
for (int i = 0; i < m; i++){
int u = G[i].first.first;
int v = G[i].first.second;
int c = G[i].second.first;
adjlist[u].push_back({v,c});
}
memset(dist,-1,sizeof(dist));
dist[1] = 0;
pq.push({0,1});
while (pq.size()){
ii cur = pq.top(); pq.pop();
int d = cur.first, u = cur.second;
if (dist[u] < d) continue;
for (auto v: adjlist[u]){
int newdist = dist[u]+v.second;
if (dist[v.first] == -1 || newdist < dist[v.first]){
dist[v.first] = newdist;
pq.push({dist[v.first],v.first});
}
}
}
int L = dist[n];
memset(dist,-1,sizeof(dist));
dist[n] = 0;
pq.push({0,n});
while (pq.size()){
ii cur = pq.top(); pq.pop();
int d = cur.first, u = cur.second;
if (dist[u] < d) continue;
for (auto v: adjlist[u]){
int newdist = dist[u]+v.second;
if (dist[v.first] == -1 || newdist < dist[v.first]){
dist[v.first] = newdist;
pq.push({dist[v.first],v.first});
}
}
}
int R = dist[1];
if (L == -1 || R == -1) return -1;
else return L+R;
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 0; i < m; i++){
int u,v,c,d;
scanf("%d%d%d%d",&u,&v,&c,&d);
G[i].first.first = u;
G[i].first.second = v;
G[i].second.first = c;
G[i].second.second = d;
}
int x = test();
//printf("noflip, %d\n",x);
if (x != -1) ans = min(ans,x);
for (int i = 0; i< m; i++){
int cost = G[i].second.second;
swap(G[i].first.first,G[i].first.second);
int r = test();
swap(G[i].first.first,G[i].first.second);
//printf("%d %d\n",cost,r);
if (r == -1) continue;
ans = min(ans,cost+r);
}
if (ans == 2000000000){
printf("-1");
return 0;
}
else printf("%d \n",ans);
}
