#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct EDGE {
int u, v, c, w;
};
void solve() {
int n, m;
cin >> n >> m;
vector<EDGE> edges(m);
vector<map<int, ll>> sum(n);
vector<map<int, VPI>> gp(n);
for (auto&[u, v, c, w] : edges) {
cin >> u >> v >> c >> w;
u--, v--;
gp[u][c].pb({v, w});
gp[v][c].pb({u, w});
sum[u][c] += w;
sum[v][c] += w;
}
priority_queue<pair<ll, PII>> pq;
/*distance, {node, prev color}*/
map<PII, ll> dist;
map<PII, bool> vis;
pq.push({0, {0, 0}});
dist[{0, 0}] = 0;
while (pq.size()) {
int u, c;
tie(u, c) = pq.top().ss;
pq.pop();
if (vis[{u, c}]) continue;
vis[{u, c}] = true;
if (c == 0) {
for (auto& P : gp[u]) {
int c = P.ff;
for (auto[v, w] : P.ss) {
ll case1 = dist[{u, 0}] + min(1ll*w, sum[u][c] - w);
if (!dist.count({v, 0}) || case1 < dist[{v, 0}]) {
dist[{v, 0}] = case1;
pq.push({-dist[{v, 0}], {v, 0}});
}
ll case2 = dist[{u, 0}];
if (!dist.count({v, c}) || case2 < dist[{v, c}]) {
dist[{v, c}] = case2;
pq.push({-dist[{v, c}], {v, c}});
}
}
}
} else {
for (auto[v, w] : gp[u][c]) {
ll case3 = dist[{u, c}] + sum[u][c] - w;
if (!dist.count({v, 0}) || case3 < dist[{v, 0}]) {
dist[{v, 0}] = case3;
pq.push({-dist[{v, 0}], {v, 0}});
}
}
}
}
if (dist.count({n-1, 0})) cout << dist[{n-1, 0}] << endl;
else cout << -1 << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1;
/*cin >> t;*/
while (t--) solve();
}
