#include <iostream>
// #include <fstream>
// std::ifstream cin ("hopscotch.in");
// std::ofstream cout ("hopscotch.out");
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <iterator>
#include <complex>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define f first
#define s second
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
typedef uint64_t hash_t;
ll const inf = (ll) 1e15 + 7;
int const M = (ll) 1e9 + 7;
int const IM = (ll) 5e8 + 4;
struct stuff {
ll x, y, z;
};
auto cmp = [](auto x, auto y) { return x.z > y.z; };
int main() {
int n, m; cin >> n >> m;
vector<map<int, vector<stuff>>> a(n);
vector<map<int, ll>> b(n);
for(int i = 0; i < m; i++) {
ll x, y, z, p; cin >> x >> y >> z >> p;
x--, y--;
a[x][0].push_back({y, z, p});
a[x][z].push_back({y, z, p});
b[x][0] += p;
b[x][z] += p;
a[y][0].push_back({x, z, p});
a[y][z].push_back({x, z, p});
b[y][0] += p;
b[y][z] += p;
}
vector<map<ll, ll>> dp(n);
priority_queue<stuff, vector<stuff>, decltype(cmp)> q(cmp);
q.push({0, 0, 0});
while(!q.empty()) {
auto u = q.top(); q.pop();
if(dp[u.x].count(u.y) && dp[u.x][u.y] <= u.z) continue;
dp[u.x][u.y] = u.z;
for(auto &l : a[u.x][u.y]) {
q.push({l.x, 0, u.z + b[u.x][u.y] - l.z});
if(u.y == 0) {
q.push({l.x, 0, u.z + l.z});
q.push({l.x, l.y, u.z});
}
}
}
cout << (!dp[n - 1].count(0) || dp[n - 1][0] == inf ? -1 : dp[n - 1][0]);
}
