#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const ll oo=0x3f3f3f3f3f3f3f3f;
template<class T>
using vvector = vector<vector<T>>;
struct edge {
ll a,b,c,d;
};
ll dijkstra(int st,int ed,vvector<pii> &G,vector<edge> &E,int rid,int n) {
vector<ll> dis(n+1,oo);
vector<bool> vis(n+1);
priority_queue<pll> pq;
dis[st]=0;
pq.emplace(0,st);
while (!pq.empty()) {
while (!pq.empty() and vis[pq.top().S]) pq.pop();
if (pq.empty()) break;
auto [d,v]=pq.top();
pq.pop();
vis[v]=true;
for (auto [i,id]:G[v]) {
if (id==rid) continue;
if (vis[i]) continue;
if (dis[i]>dis[v]+E[id].c) {
dis[i]=dis[v]+E[id].c;
pq.emplace(-dis[i],i);
}
}
if (E[rid].b==v) {
int i=E[rid].a;
int id=rid;
if (vis[i]) continue;
if (dis[i]>dis[v]+E[id].c) {
dis[i]=dis[v]+E[id].c;
pq.emplace(-dis[i],i);
}
}
}
return dis[ed];
}
int main() {
speed;
int n,m;
cin>>n>>m;
vector<edge> E(m+1);
vvector<pii> G(n+1);
for (int i=1;i<=m;i++) {
ll a,b,c,d;
cin>>a>>b>>c>>d;
G[a].emplace_back(b,i);
E[i]={a,b,c,d};
}
ll ans=oo;
for (int i=0;i<=m;i++) {
ll now=E[i].d+dijkstra(1,n,G,E,i,n)+dijkstra(n,1,G,E,i,n);
ans=min(ans,now);
}
cout<<(ans==oo?-1:ans)<<"\n";
return 0;
}
