#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
struct kraw {
int a;
int v;
int c;
ll p;
};
const int MAXN = 100 * 1000 + 1;
const int MAXM = 200 * 1000 + 1;
bool odw[MAXN];
vector<kraw> graf[MAXN];
priority_queue<pli> pq;
ll odl[MAXN];
ll suma[MAXM];
ll minn[MAXM];
int main () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, a, b;
cin >> n >> m;
kraw x;
for (int i = 0; i < m; i ++) {
cin >> x.a >> x.v >> x.c >> x.p;
graf[x.a].pb(x);
swap(x.a, x.v);
graf[x.a].pb(x);
}
for (int i = 1; i <= n; i ++) {
odl[i] = LLONG_MAX/ll(1000);
}
pq.push({0, 1});
odl[1] = 0;
while (!pq.empty()) {
ll aktodl = -pq.top().st;
int v = pq.top().nd;
pq.pop();
if (odw[v]) {
continue;
}
odw[v] = true;
for (auto x : graf[v]) {
suma[x.c] = 0LL;
minn[x.c] = LLONG_MAX/ll(1000);
}
for (auto x : graf[v]) {
suma[x.c] += x.p;
}
for (auto x : graf[v]) {
minn[x.c] = min(minn[x.c], odl[x.v] + suma[x.c]);
}
for (auto u : graf[v]) {
// zmien kolor zmien wszystkie tego koloru oprocz tej
ll x = min({odl[v] + u.p, odl[v] + suma[u.c] - u.p, minn[u.c] - u.p});
if (x < odl[u.v]) {
odl[u.v] = x;
pq.push({-x, u.v});
}
}
}
if (odl[n] >= LLONG_MAX/ll(1000)) {
cout << -1 << "\n";
return 0;
}
cout << odl[n] << "\n";
return 0;
}
