/* code by the cute ~~Dengdualang~~ PixelCat owo */
/* as cute as nacho neko (aka. my wife)! */
/* Nhade stay for a night here */
/* 183234 deng deng deng pixelcat oops */
/* (yang wang yesu)*2 */
/* ^ some weird stuff. nvm =w= */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL //__int128
#define double long double
using namespace std;
using LL = long long;
using LLL = __int128_t;
using uLL = unsigned long long;
using pii = pair<int, int>;
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair
#define MOD (int)(998244353)
// #define MOD (int)((LL)1e9 + 7)
#define INF (int)(4e18)
// #define INF 1e9
#define EPS (1e-6)
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
#endif
inline void NYA() {
ios::sync_with_stdio(false);
cin.tie(0);
}
inline int gcd(int a, int b) {
return __gcd(a, b);
}
inline int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
int ans = 1;
while (p) {
if (p & 1) ans = ans * b % mod;
p >>= 1;
b = b * b % mod;
}
return ans;
}
int fpow(int b, int p) {
return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
if (_b > _a) _a = _b;
}
// mt19937_64 rng(
// chrono::steady_clock::now().time_since_epoch().count());
struct Edge{
int s,t,c,d;
}ed[50050];
int tag[50050];
vector<int> adj[210];
int ad[210][210];
int dist[210];
int src[210];
int dijk(int s,int t,int nope,int tg){
// debug(s,t);
if(nope>0){
ed[0]=ed[nope];
swap(ed[0].s,ed[0].t);
adj[ed[0].s].eb(0);
}
memset(dist,0x3f3f3f3f,sizeof(dist));
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.emplace(0,s);
dist[s]=0;
while(!pq.empty()){
int d=pq.top().F;
int now=pq.top().S;
pq.pop();
if(dist[now]<d) continue;
for(auto &eid:adj[now]) if(eid!=nope){
auto &e=ed[eid];
if(dist[e.t]>d+e.c){
dist[e.t]=d+e.c;
pq.emplace(d+e.c,e.t);
src[e.t]=eid;
}
}
}
if(nope>0){
adj[ed[0].s].pop_back();
}
if(dist[t]>=INF) return INF;
if(tg){
int now=t;
while(now!=s){
tag[src[now]]^=tg;
now=ed[src[now]].s;
}
}
return dist[t];
}
int32_t main() {
NYA();
// nyaacho >/////<
// miku sama bless me >/////<
int n,m; cin>>n>>m;
memset(ad,0x3f3f3f3f,sizeof(ad));
For(i,1,n) ad[i][i]=0;
For(i,1,m){
auto &e=ed[i];
cin>>e.s>>e.t>>e.c>>e.d;
adj[e.s].eb(i);
chmin(ad[e.s][e.t],e.c);
}
For(k,1,n) For(i,1,n) For(j,1,n){
chmin(ad[i][j],ad[i][k]+ad[k][j]);
}
int m1n=dijk(1,n,-1,1);
int mn1=dijk(n,1,-1,2);
int ans=m1n+mn1;
For(eid,1,m){
auto &e=ed[eid];
int d1n,dn1;
if(tag[eid]&1) d1n=dijk(1,n,eid,0);
else d1n=min(m1n,ad[1][e.t]+ad[e.s][n]+e.c);
if(tag[eid]&2) dn1=dijk(n,1,eid,0);
else dn1=min(mn1,ad[n][e.t]+ad[e.s][1]+e.c);
chmin(ans,d1n+dn1+e.d);
// debug(eid,d1n,dn1);
}
if(ans>=INF) cout<<"-1\n";
else cout<<ans<<"\n";
return 0;
}
