#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
vector<tuple<int,int,int>> adj[200], radj[200];
vector<tuple<int,int,int,int,int>> E;
int N, P[200];
long long dist1[200], dist2[200], rdist1[200], rdist2[200], dist[200];
bool MP[2][50000];
void dijkstra(int c, long long *dist, vector<tuple<int,int,int>> *adj)
{
priority_queue<pair<long long,int>> Q;
for(int i=0;i<N;i++) {
dist[i]=(i!=c)*0x1f1f1f1f1f1f1f1fLL;
P[i]=-1;
}
Q.emplace(0,c);
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
if(-t!=dist[c]) continue;
for(auto[n,w,i]: adj[c]) if(dist[n]>dist[c]+w) {
dist[n]=dist[c]+w;
P[n]=i;
Q.emplace(-dist[n],n);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int M;
long long ans;
priority_queue<pair<long long,int>> Q;
cin>>N>>M;
E.resize(M);
for(int i=0;i<M;i++) {
auto &[u,v,w,x,idx]=E[i];
cin>>u>>v>>x>>w; idx=i;
adj[--u].emplace_back(--v,x,i);
radj[v].emplace_back(u,x,i);
}
dijkstra(N-1,dist2,radj); dijkstra(0,dist1,adj);
for(int c=0;c<N;c++) if(P[c]>-1) MP[0][P[c]]=true;
dijkstra(0,rdist2,radj); dijkstra(N-1,rdist1,adj);
for(int c=0;c<N;c++) if(P[c]>-1) MP[1][P[c]]=true;
ans=dist1[N-1]+rdist1[0];
for(auto[u,v,w,x,i]: E) {
long long res=w;
if(MP[0][i]) {
for(int i=0;i<N;i++) dist[i]=(i!=0)*0x1f1f1f1f1f1f1f1fLL;
Q.emplace(0,0);
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
if(-t!=dist[c]) continue;
if(c==v && dist[u]>dist[v]+x) {
dist[u]=dist[v]+x;
Q.emplace(-dist[u],u);
}
for(auto[n,w,j]: adj[c]) if(i!=j && dist[n]>dist[c]+w) {
dist[n]=dist[c]+w;
Q.emplace(-dist[n],n);
}
}
res+=dist[N-1];
}
else res+=min(dist1[N-1],dist1[v]+dist2[u]+x);
if(MP[1][i]) {
for(int i=0;i<N;i++) dist[i]=(i!=N-1)*0x1f1f1f1f1f1f1f1fLL;
Q.emplace(0,N-1);
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
if(-t!=dist[c]) continue;
if(c==v && dist[u]>dist[v]+x) {
dist[u]=dist[v]+x;
Q.emplace(-dist[u],u);
}
for(auto[n,w,j]: adj[c]) if(i!=j && dist[n]>dist[c]+w) {
dist[n]=dist[c]+w;
Q.emplace(-dist[n],n);
}
}
res+=dist[0];
}
else res+=min(rdist1[0],rdist1[v]+rdist2[u]+x);
ans=min(ans,res);
}
cout<<(ans<0x1f1f1f1f1f1f1f1fLL ? ans:-1)<<'\n';
return 0;
}
