#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m;
vector<pll> adj[100005];
pair<pll, pll> edj[200005];
pll reft[200005];
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
pll dist[200005][2];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
iloop(0, m) {
cin >> edj[i].second.first >> edj[i].second.second >> edj[i].first.first >> edj[i].first.second;
edj[i].second.first--, edj[i].second.second--;
reft[i] = {adj[edj[i].second.first].size(), adj[edj[i].second.second].size()};
adj[edj[i].second.first].push_back({i, edj[i].second.second});
adj[edj[i].second.second].push_back({i, edj[i].second.first});
}
iloop(0, n) jloop(0, 2) dist[i][j] = {INF, -1};
dist[0][0] = {0, -1};
pq.push({0, {0, 0}});
while (pq.size()) {
pair<ll, pll> nd = pq.top();
pq.pop();
if (dist[nd.second.first][nd.second.second].first != nd.first) continue;
if (nd.second.second == 0) {
gp_hash_table<ll, ll> gp;
for (auto it : adj[nd.second.first]) {
gp[edj[it.first].first.first] += edj[it.first].first.second;
}
for (auto it : adj[nd.second.first]) {
if (dist[it.second][1].first > nd.first + edj[it.first].first.second) {
dist[it.second][1].first = nd.first + edj[it.first].first.second;
if (edj[it.first].second.first == nd.second.first) dist[it.second][1].second = reft[it.first].second;
else dist[it.second][1].second = reft[it.first].first;
pq.push({dist[it.second][1].first, {it.second, 1}});
}
if (dist[it.second][0].first > nd.first + gp[edj[it.first].first.first] - edj[it.first].first.second) {
dist[it.second][0].first = nd.first + gp[edj[it.first].first.first] - edj[it.first].first.second;
pq.push({dist[it.second][0].first, {it.second, 0}});
}
}
}
else {
gp_hash_table<ll, ll> gp;
iloop(0, (ll)adj[nd.second.first].size()) if (i != dist[nd.second.first][1].second) {
pll it = adj[nd.second.first][i];
gp[edj[it.first].first.first] += edj[it.first].first.second;
}
iloop(0, (ll)adj[nd.second.first].size()) {
if (i == dist[nd.second.first][1].second) continue;
pll it = adj[nd.second.first][i];
if (dist[it.second][1].first > nd.first + edj[it.first].first.second) {
dist[it.second][1].first = nd.first + edj[it.first].first.second;
if (edj[it.first].second.first == nd.second.first) dist[it.second][1].second = reft[it.first].second;
else dist[it.second][1].second = reft[it.first].first;
pq.push({dist[it.second][1].first, {it.second, 1}});
}
if (dist[it.second][0].first > nd.first + gp[edj[it.first].first.first] - edj[it.first].first.second) {
dist[it.second][0].first = nd.first + gp[edj[it.first].first.first] - edj[it.first].first.second;
pq.push({dist[it.second][0].first, {it.second, 0}});
}
}
}
}
ll cans = min(dist[n-1][0].first, dist[n-1][1].first);
cout << (cans == INF ? -1 : cans);
}
