#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define chmin(a, b) a = min(a,b)
#define chmax(a,b) a = max(a,b)
using T = pair<ll,pii>;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, m, a, b, c, p; cin >> n >> m;
vector<map<int,ll>> trsn(n), sum(n);
vector<ll> dist(n,LLONG_MAX); // self, complement
vector<vector<T>> adj(n);
F0R(i,m) {
cin >> a >> b >> c >> p; a--; b--;
adj[a].pb({b,{c,p}});
adj[b].pb({a,{c,p}});
trsn[a][c] = trsn[b][c] = LLONG_MAX;
sum[a][c] += p; sum[b][c] += p;
}
priority_queue<T,vector<T>,greater<T>> pq; // dist, node, color [1,m], 0 for unspecified color
// t->c, c->c, s->s, c->s->t
dist[0] = 0;
pq.push({0,{0,0}});
//for(auto& x : trsn[0]) {x.s = 0; pq.push({0,{0,x.f}});}
while (pq.size()) {
auto[d,z] = pq.top(); pq.pop();
auto[cur,t] = z;
if ((!t && dist[cur]!=d) || (t && trsn[cur][t]!=d)) {continue;}
/*
self->complement is to any colors such that they are not the
color you came from, but you don't care because if you transition to
the same color you get an unoptimal answer that you will rectify
with transition->complement
so self and complement push to the same thing, so combine them
*/
for (T z : adj[cur]) {
auto[x,y] = z; auto[c,p] = y;
if (!t) { // push to (self, complement), and transition
if (d+p<dist[x]) {pq.push({dist[x]=d+p,{x,0}});}
if (d+sum[cur][c]-p<dist[x]) {pq.push({dist[x]=d+sum[cur][c]-p,{x,0}});}
if (d<trsn[x][c]) {pq.push({trsn[x][c]=d,{x,c}});}
//cout<<dist[2]<<'\n';
} else if (t==c) { // push to complement
//cout << sum[cur][c]-p << '\n';
//cout << x+1 << " " << c << '\n';
if (sum[cur][c]+d-p<dist[x]) {pq.push({dist[x]=sum[cur][c]+d-p,{x,0}});}
}
}
} cout << (dist[n-1]==LLONG_MAX ? -1 : dist[n-1]) << '\n';
//cout<<dist[3]<<'\n';
}
