/// KoJa
#include <bits/stdc++.h>
using namespace std;
#define task "QG04PAINT"
#define pb push_back
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
#define BIT(a) (1LL << (a))
#define vec vector
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, int> ii;
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
void init()
{
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
void fastio()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
}
const int N = int(5e5) + 1000;
const ll INF = 1e18;
int n, m;
ll dist[N], best[N], sum[N];
struct Edge
{
int v, c, cost;
Edge() {}
Edge(int _v, int _c, int _cost)
{
v = _v;
c = _c;
cost = _cost;
}
};
vec<Edge> adj[N];
int main()
{
fastio();
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, c, cost;
cin >> u >> v >> c >> cost;
adj[u].pb(Edge(v, c, cost));
adj[v].pb(Edge(u, c, cost));
}
for (int i = 1; i <= n; i++)
dist[i] = INF;
for (int i = 1; i <= m; i++)
best[i] = INF;
dist[1] = 0;
priority_queue<pair<ll, int>> q;
q.push(make_pair(0LL, 1));
while (!q.empty())
{
int u = q.top().se;
ll cur = -q.top().fi;
// cout << u << " " << -du << '\n';
q.pop();
if (cur != dist[u])
continue;
for (Edge x : adj[u])
{
sum[x.c] += x.cost;
best[x.c] = min(best[x.c], dist[x.v]);
}
for (Edge x : adj[u])
{
int v = x.v;
int c = x.c;
int cost = x.cost;
ll tmp = min(cost + 0LL, sum[c] - cost);
if (minimize(dist[v], tmp + cur))
q.push(make_pair(-dist[v], v));
if (minimize(dist[v], best[c] + sum[c] - cost))
q.push(make_pair(-dist[v], v));
}
for (Edge x : adj[u])
{
sum[x.c] = 0;
best[x.c] = INF;
}
}
if (dist[n] == INF)
dist[n] = -1;
cout << dist[n];
return 0;
}
