#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;
gp_hash_table<ll, ll> dist[200005];
map<ll, vector<pll>> mp[200005];
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});
dist[edj[i].second.first][edj[i].first.first] = INF;
dist[edj[i].second.second][edj[i].first.first] = INF;
mp[edj[i].second.first][edj[i].first.first].push_back({i, edj[i].second.second});
mp[edj[i].second.second][edj[i].first.first].push_back({i, edj[i].second.first});
}
iloop(0, n) dist[i][0] = INF;
dist[0][0] = 0;
pq.push({0, {0, 0}});
while (pq.size()) {
pair<ll, pll> nd = pq.top();
pq.pop();
if (dist[nd.second.first][nd.second.second] != 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][0] > nd.first + edj[it.first].first.second) {
dist[it.second][0] = nd.first + edj[it.first].first.second;
pq.push({dist[it.second][0], {it.second, 0}});
}
if (dist[it.second][0] > nd.first + gp[edj[it.first].first.first] - edj[it.first].first.second) {
dist[it.second][0] = nd.first + gp[edj[it.first].first.first] - edj[it.first].first.second;
pq.push({dist[it.second][0], {it.second, 0}});
}
if (dist[it.second][edj[it.first].first.first] > nd.first) {
dist[it.second][edj[it.first].first.first] = nd.first;
pq.push({dist[it.second][edj[it.first].first.first], {it.second, edj[it.first].first.first}});
}
}
}
else {
ll cs = 0;
for (auto it : mp[nd.second.first][nd.second.second]) cs += edj[it.first].first.second;
for (auto it : mp[nd.second.first][nd.second.second]) {
if (dist[it.second][0] > nd.first + cs - edj[it.first].first.second) {
dist[it.second][0] = nd.first + cs - edj[it.first].first.second;
pq.push({dist[it.second][0], {it.second, 0}});
}
}
}
}
cout << (dist[n-1][0] == INF ? -1 : dist[n-1][0]);
}
