// composite - yosupo
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
const ll mod = 998244353;
using namespace std;
const int N = 1e5+5;
const ll inf = 1e15;
struct Edge {
int v, color, cost;
bool paid = 0;
};
vector<Edge> adj[N];
map<pii, int> colorcnt;
map<pii, int> colorsum;
void solve() {
int n, m;
cin >> n >> m;
F(i, 0, m) {
int _, __, ___, ____;
cin >> _ >> __ >> ___ >> ____;
_--, __--;
adj[_].push_back({__, ___, ____});
adj[__].push_back({_, ___, ____});
colorcnt[{_, ___}]++;
colorcnt[{__, ___}]++;
colorsum[{_, ___}] += ____;
colorsum[{__, ___}] += ____;
}
F(i, 0, n) {
for(auto &edge : adj[i]) if(colorcnt[{i, edge.color}] > 1) {
edge.paid = 1;
}
}
#define State pair<int, pii>
// node, {last_color, w}
map<State, int> dist;
priority_queue<pair<int, State>> pq;
dist[{0, {-1, 0}}] = inf;
pq.push({inf, {0, {-1, 0}}});
int ans = 0;
while(!pq.empty()) {
auto cur = pq.top();
pq.pop();
int dst = cur.fi, node = cur.se.fi, last_color = cur.se.se.fi, last_w = cur.se.se.se;
if(dist[{node, {last_color, last_w}}] > dst) continue;
if(node == n-1) ans = max(ans, dst);
for(auto &edge : adj[node]) {
/*int cost = edge.color == last_color && colorcnt[{node, last_color}] == 2 ? 0 : edge.cost;
int new_last = cost ? edge.color : -1;
if(dist[{edge.v, new_last}] < dst - cost) {
dist[{edge.v, new_last}] = dst - cost;
pq.push({dist[{edge.v, new_last}], {edge.v, new_last}});
}*/
int convertAll = colorsum[{node, edge.color}] - edge.cost;
if(edge.color == last_color) convertAll -= last_w;
State takestate = {edge.v, {edge.color, edge.cost}};
int takecost = dst - edge.cost;
State passstate = {edge.v, {-1, 0}};
int passcost = min(dst, dst - convertAll);
//cout << node sp edge.v sp edge.cost sp last_color sp last_w sp convertAll sp colorsum[{node, edge.color}] sp inf - takecost sp inf - passcost << endl;
if(dist[passstate] < passcost) {
dist[passstate] = passcost;
pq.push({passcost, passstate});
}
if(dist[takestate] < takecost) {
dist[takestate] = takecost;
pq.push({takecost, takestate});
}
}
}
cout << (ans == 0 ? -1 : inf - ans) << endl;
}
int32_t main() {
cin.tie(0); ios_base::sync_with_stdio(0);
#ifdef Local
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while(t--) solve();
}
