#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
struct node {
ll dis;
int u, c;
node() {}
node(int _u, int _c, ll _d) { u = _u, c = _c, dis = _d; }
friend bool operator < (node a, node b) { return a.dis > b.dis; }
};
priority_queue<node> Q;
const int maxn = 100005;
const int maxm = 400005;
int last[maxn], Next[maxm], to[maxm], w[maxm], col[maxm], cnt;
unordered_map <int, ll> Map[maxn], sum[maxn];
unordered_map <int, vector<pair<int, int> > > out[maxn];
inline void addedge(int x, int y, int z, int c) {
Next[++cnt] = last[x], last[x] = cnt;
to[cnt] = y, w[cnt] = z, col[cnt] = c;
out[x][c].push_back(make_pair(y, z));
sum[x][c] += z;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1, x, y, z, c; i <= m; i++) {
scanf("%d%d%d%d", &x, &y, &c, &z);
addedge(x, y, z, c), addedge(y, x, z, c);
}
auto check = [=] (int u, int c, ll dis) -> void {
if(!Map[u].count(c) || Map[u][c] > dis)
Map[u][c] = dis, Q.push(node(u, c, dis));
};
check(1, 0, 0);
while(!Q.empty()) {
node tmp = Q.top();
Q.pop();
int u = tmp.u, c = tmp.c;
ll dis = tmp.dis;
if(Map[u][c] != dis) continue;
if(!c) {
for(int i = last[u]; i; i = Next[i]) {
int v = to[i];
check(v, col[i], dis);
check(v, 0, dis + min(sum[u][col[i]] - w[i], (ll)w[i]));
}
}
else {
if(out[u].count(c)) {
for(auto tp : out[u][c]) {
int v = tp.first, w = tp.second;
check(v, 0, dis + sum[u][c] - w);
}
}
}
}
Map[n].count(0) ? printf("%lld\n", Map[n][0]) : puts("-1");
return 0;
}
