#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair <int, int> ii;
const int N = 2e5 + 1;
const int mod = 998244353;
struct datas {
int ver, c, d;
};
vector <datas> ed[N];
void solve() {
int n, m; cin >> n >> m;
map <ii, ll> sve;
for(int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
ed[u].push_back({v, c, d});
ed[v].push_back({u, c, d});
sve[{u, c}] += d;
sve[{v, c}] += d;
}
priority_queue <pair <ll, pair <map <ii, ll>, int>>, vector <pair <ll, pair <map <ii, ll>, int>>>, greater <pair <ll, pair <map <ii, ll>, int>>>> pq;
vector <ll> dp(n + 1, 1e18);
map <ii, ll> mp;
pq.push({0, {mp, 1}});
dp[1] = 0;
while (sz(pq)) {
ll d = pq.top().f;
map <ii, ll> save = pq.top().s.f;
int u = pq.top().s.s;
pq.pop();
if (dp[u] != d) continue;
for(auto x: ed[u]) {
int v = x.ver, c = x.c;
ll _d = x.d;
if (sve[{u, c}] - save[{u, c}] >= _d)
_d = min(_d, sve[{u, c}] - save[{u, c}] - _d);
if (dp[v] > dp[u] + _d) {
map <ii, ll> _save;
if (x.d == _d)
_save[{v, c}] += _d;
dp[v] = dp[u] + _d;
pq.push({dp[v], {_save, v}});
}
}
}
cout << (dp[n] != 1e18 ? dp[n] : -1) << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("ROBOT.INP", "r", stdin);
// freopen("ROBOT.OUT", "w", stdout);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
