#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (int)(x).size()
#define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
template<class T1 , class T2>
bool maximize(T1 &a , T2 b){
if (a < b) return a = b , true; else return false;
}
template<class T1 , class T2>
bool minimize(T1 &a , T2 b){
if (a > b) return a = b , true; else return false;
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() , data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class T1 , class T2>
T2 Find(const vector<T1>&data , T2 y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
const int N = (int) 200;
const int M = (int) 5e4;
const LL inf = (LL)1e18;
int x[M + 2] , y[M + 2] , c[M + 2] , d[M + 2];
int n , m;
vector<int> ke[N + 2][2];
void add_canh(int u , int v , int id , int t){
ke[u][t].push_back(id);
return;
}
LL dist[N + 2][M + 2][2] = {};
struct Node{
LL cost;
int u , id_canh;
bool change_canh;
bool operator < (const Node&other) const{
return cost > other.cost;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
cin >> x[i] >> y[i] >> c[i] >> d[i];
add_canh(x[i] , y[i] , i , 0);
add_canh(y[i] , x[i] , i , 1);
}
memset(dist , 0x3f , sizeof dist);
priority_queue<Node> pq;
dist[1][0][0] = 0;
pq.push({dist[1][0][0] , 1 , 0 , 0});
while (pq.size()){
int u = pq.top().u , _id = pq.top().id_canh ;
bool tt = pq.top().change_canh;
LL cost = pq.top().cost;
pq.pop();
if (cost != dist[u][_id][tt]) continue;
if (_id == 0 && tt == 0){
for(int id : ke[u][1]){
int v = u ^ x[id] ^ y[id];
if (minimize(dist[v][id][0] , cost + c[id] + d[id])) pq.push({dist[v][id][0] , v , id , 0});
}
for(int id : ke[u][0]){
int v = u ^ x[id] ^ y[id];
if (minimize(dist[u][id][1] , cost + d[id])) pq.push({dist[u][id][1] , u , id , 1});
}
}
for(int id : ke[u][0]){
if (id == _id) continue;
int v = x[id] ^ y[id] ^ u;
if (minimize(dist[v][_id][tt] , cost + c[id])) pq.push({dist[v][_id][tt] , v , _id , tt});
}
}
for(int i = 1; i < n; ++i){
for(int j = 0; j <= m; ++j) dist[i][j][0] = dist[i][j][1] = inf;
}
for(int i = 0; i <= m; ++i){
pq.push({dist[n][i][0] , n , i , 0});
pq.push({dist[n][i][1] , n , i , 1});
}
while (pq.size()){
int u = pq.top().u , _id = pq.top().id_canh;
bool tt = pq.top().change_canh;
LL cost = pq.top().cost;
pq.pop();
if (cost != dist[u][_id][tt]) continue;
// cout << u << ' ' << _id << ' ' << tt << " COST : " << cost << '\n';
if (tt == 1){
for(int id : ke[u][1]){
if (id != _id) continue;
int v = u ^ x[id] ^ y[id];
if (minimize(dist[v][_id][tt] , cost + c[id])) pq.push({dist[v][_id][tt] , v , _id , tt});
}
}
for(int id : ke[u][0]){
if (id == _id) continue;
int v = u ^ x[id] ^ y[id];
if (minimize(dist[v][_id][tt] , cost + c[id])) pq.push({dist[v][_id][tt] , v , _id , tt});
}
}
LL ans = inf;
for(int i = 0; i <= m; ++i) {
minimize(ans , dist[1][i][0]);
minimize(ans , dist[1][i][1]);
}
if (ans == inf) ans = -1;
cout << ans;
return 0;
}
