#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]
);
}
}
}
multiset<int>v[n][n];
for(int i=0;i<m;i++){
v[all[i].x][all[i].y].insert(all[i].c);
if(2<v[all[i].x][all[i].y].size()){
auto p=v[all[i].x][all[i].y].end();
p--;
v[all[i].x][all[i].y].erase(p);
}
}
//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;
//cerr<<dist[y][x]-c<<" "<<(dist[0][n-1]+dist[n-1][0])-ans<<"\n";
auto p=v[x][y].find(c);
if(p!=v[x][y].end())v[x][y].erase(v[x][y].find(c));
v[y][x].insert(c);
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)break;
for(int j=0;j<n;j++){
if(v[mini][j].size()){
curd[j]=min(
curd[j],
curd[mini]+*v[mini][j].begin()
);
}
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[n-1]==inf){
v[y][x].erase(v[y][x].find(c));
v[x][y].insert(c);
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)break;
for(int j=0;j<n;j++){
if(v[mini][j].size()){
curd[j]=min(
curd[j],
curd[mini]+*v[mini][j].begin()
);
}
}
}
/*
for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
cerr<<"\n";
*/
if(curd[0]!=inf){
ansnow+=curd[0]+d;
ans=min(ans,ansnow);
}
//cerr<<ansnow<<"\n\n";
p=v[y][x].find(c);
if(p!=v[y][x].end()){
v[y][x].erase(v[y][x].find(c));
}
v[x][y].insert(c);
}
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();
}
}
