#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=2e5+5;
#else
const int lim=3e3+3;
#endif
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int mod=1e9+7;
//const int mod=(1ll<<61)-1;
using pii=pair<int,int>;
struct edge{
int x,y,c,d;
};
template <>
struct std::hash<pii>{
size_t operator()(const pii& k) const{
int first=hash<int>()(k.first),second=hash<int>()(k.second);
return hash<int>()(first^second);
}
};
const int inf=INT_MAX*200ll;
inline void solve(){
int n,m;
cin>>n>>m;
edge all[m];
for(int i=0;i<m;i++){
cin>>all[i].x>>all[i].y>>all[i].c>>all[i].d;
all[i].x--,all[i].y--;
}
int dist[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[i][j]=inf;
}
}
for(int i=0;i<m;i++){
dist[all[i].x][all[i].y]=min(
all[i].c,
dist[all[i].x][all[i].y]
);
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[i][j]=min(
dist[i][j],
dist[i][k]+dist[k][j]
);
}
}
}
pii v[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
v[i][j]={inf,inf};
}
}
for(auto[x,y,c,d]:all){
if(c<v[x][y].second){
v[x][y].second=c;
if(v[x][y].second<v[x][y].first){
swap(v[x][y].first,v[x][y].second);
}
}
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cerr<<(v[i][j].first^inf?v[i][j].first:-1)<<" "<<(v[i][j].second^inf?v[i][j].second:-1)<<" | ";
}cerr<<"\n";
}
*/
//cerr<<"ok\n";
int ans=dist[0][n-1]+dist[n-1][0];
//cerr<<ans<<"\n";
for(auto[x,y,c,d]:all){
//cerr<<"\n"<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n";
if(dist[y][x]<=c)continue;
if(dist[y][x]-c<=(dist[0][n-1]+dist[n-1][0])-ans)continue;
//cerr<<dist[y][x]-c<<" "<<(dist[0][n-1]+dist[n-1][0])-ans<<"\n";
pii p1=v[x][y],p2=v[y][x];
if(v[x][y].first==c){
swap(v[x][y].first,v[x][y].second);
}
if(c<v[y][x].second){
v[y][x].second=c;
if(v[y][x].second<v[y][x].first){
swap(v[y][x].first,v[y][x].second);
}
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cerr<<(v[i][j].first^inf?v[i][j].first:-1)<<" | ";
}cerr<<"\n";
}
*/
int curd[n];
for(int i=0;i<n;i++){
curd[i]=inf;
}
curd[0]=0;
bool vis[n];
memset(vis,0,sizeof(vis));
for(int i=0;i<n-1;i++){
int mini=-1;
for(int j=0;j<n;j++){
if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
mini=j;
}
}
vis[mini]=1;
if(mini==n-1||ans<curd[mini]+d)break;
for(int j=0;j<n;j++){
curd[j]=min(
curd[j],
curd[mini]+v[mini][j].first
);
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[n-1]==inf){
v[x][y]=p1;
v[y][x]=p2;
continue;
}
int ansnow=curd[n-1];
for(int i=0;i<n;i++){
curd[i]=inf;
}
curd[n-1]=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n-1;i++){
int mini=-1;
for(int j=0;j<n;j++){
if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
mini=j;
}
}
vis[mini]=1;
if(!mini||ans<ansnow+curd[mini]+d)break;
for(int j=0;j<n;j++){
curd[j]=min(
curd[j],
curd[mini]+v[mini][j].first
);
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[0]!=inf){
ansnow+=curd[0]+d;
//cerr<<ansnow<<"\n";
ans=min(ans,ansnow);
}
//cerr<<ansnow<<"\n\n";
v[x][y]=p1;
v[y][x]=p2;
}
if(ans<inf-100)cout<<ans<<"\n";
else cout<<"-1\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
