#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define siz(x) (int)(x).size()
#define pow2(x) (1ll << (x))
#define on(mask, x) ((mask >> x & 1) == 1)
#define off(mask, x) ((mask >> x & 1) == 0)
#define mp make_pair
#define vec vector
#define ar array
#define fi first
#define se second
#define pii pair<int, int>
#define out(x) cout << #x << " " << x << "\n"
template<class T> bool ckmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool ckmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0);
#define task "input"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
}
const ll LINF = 1e18+18;
const int INF = 1e9+9;
const int N = 2e5+5;
int n, m;
struct Edge {
int a[2];
ll c, p;
Edge (int _u=0, int _v=0, int _c=0, ll _p=0) {
a[0] = _u;
a[1] = _v;
c = _c;
p = _p;
}
int other(int u) {
return a[0]^a[1]^u;
}
};
vector<Edge> edges;
vector<int> adj[N];
map<int, ll> color[N];
map<int, ll> dp[N];
ll sum[N][2];
int main() {
setIO();
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, c, p;
cin >> u >> v >> c >> p;
if (u > v) swap(u, v);
adj[u].push_back(siz(edges));
adj[v].push_back(siz(edges));
edges.emplace_back(u, v, c, p);
color[u][c] += p;
color[v][c] += p;
}
priority_queue<pair<ll, pair<int, int>>> pq;
dp[1][0] = 0;
pq.push({0, {1, 0}});
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
ll w = -top.fi;
int u = top.se.fi, lst_c = top.se.se;
if (w != dp[u][lst_c]) continue;
if (u == n && lst_c == 0) {
cout << w;
return 0;
}
if (lst_c == 0) {
for (int i : adj[u]) {
int v = edges[i].other(u);
ll cost = w + min(color[u][edges[i].c] - edges[i].p, edges[i].p);
if (dp[v].find(0) == dp[v].end()) dp[v][0] = LINF;
if (dp[v].find(edges[i].c) == dp[v].end()) dp[v][edges[i].c] = LINF;
if (ckmin(dp[v][0], cost)) {
pq.push({-dp[v][0], {v, 0}});
}
if (ckmin(dp[v][edges[i].c], w)) {
pq.push({-dp[v][edges[i].c], {v, edges[i].c}});
}
}
}
else {
for (int i : adj[u]) {
int v = edges[i].other(u);
if (edges[i].c != lst_c) continue;
if (dp[v].find(0) == dp[v].end()) dp[v][0] = LINF;
if (ckmin(dp[v][0], w + color[u][edges[i].c] - edges[i].p)) {
pq.push({-dp[v][0], {v, 0}});
}
}
}
}
cout << -1;
}
