#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
#define fi first
#define se second
#define FOR(i , l , r) for(int i = (l) ; i <= (r) ; i++)
#define FOD(i , r , l) for(int i = (r) ; i >= (l) ; i--)
const int N = 2e5 + 5;
const int INF = 1e18;
int n , m;
struct node {
int v , c , p;
};
vector<node> adj[N];
int d[N];
int cnt[N];
int mn[N];
void dijikstra() {
FOR(i , 2 , n) d[i] = INF;
priority_queue<pii , vector<pii> , greater<pii>> pq;
pq.push({0 , 1});
while(pq.size()) {
int val = pq.top().fi;
int u = pq.top().se;
pq.pop();
if(d[u] < val) continue;
for(auto v : adj[u]) {
cnt[v.c] = 0;
mn[v.c] = INF;
}
for(auto v: adj[u]) {
cnt[v.c] += v.p;
}
for(auto e : adj[u]) {
mn[e.c] = min(mn[e.c] , d[e.v] + cnt[e.c]);
}
for(auto e : adj[u]) {
int v = e.v; int c = e.c ;int p = e.p;
int ans = min({mn[e.c] - p , d[u] + cnt[e.c] - p , d[u] + p });
if(ans < d[e.v]) {
d[e.v] = ans;
pq.push({d[e.v] , e.v});
}
}
}
}
void solve () {
cin >> n >> m;
FOR(i , 1 , m) {
int u , v , c , p; cin >> u >> v >>c >> p;
adj[u].push_back({v , c , p});
adj[v].push_back({u, c , p});
}
dijikstra();
cout<< (d[n] == INF ? -1 : d[n]);
}
main () {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
