#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
#define f first
#define s second
template<class T> using pqg=priority_queue<T, vector<T>, greater<T>>;
const int N=100000;
const int M=200000;
int n, m;
map<int, vector<int>> adj[N+1];
int c[M], P[M];
map<pii, pair<int, long long>> dp; //{0/1, min}
map<int, long long> sum[N+1];
pii uv[M];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; i++){
int u, v; cin >> u >> v >> c[i] >> P[i];
uv[i]={u, v};
adj[u][c[i]].push_back(i);
adj[v][c[i]].push_back(i);
adj[u][0].push_back(i);
adj[v][0].push_back(i);
sum[u][c[i]]+=P[i];
sum[v][c[i]]+=P[i];
sum[u][0]+=P[i];
sum[v][0]+=P[i];
}
pqg<pair<long long, pii>> pq;
pq.push({0, {1, 0}});
while(!pq.empty()){
pair<long long, pii> p=pq.top(); pq.pop();
if(dp[p.s].f) continue;
dp[p.s]={1, p.f};
int x=p.s.f;
if(adj[x][p.s.s].empty()) continue;
for(int e:adj[x][p.s.s]){
int k=uv[e].f==x?uv[e].s:uv[e].f;
if(p.s.s){
if(!dp[{k, 0}].f) pq.push({sum[x][c[e]]-P[e]+p.f, {k, 0}});
}
else{
if(!dp[{k, 0}].f) pq.push({min(sum[x][c[e]]-P[e], (long long)P[e])+p.f, {k, 0}});
if(!dp[{k, c[e]}].f) pq.push({p.f, {k, c[e]}});
}
}
}
if(dp[{n, 0}].f) cout <<dp[{n, 0}].s;
else cout << -1;
}
// when you recolor you're never tied to one color
// star case just works out since you've reached n before hitting the problem
// dp[i][color] - only transition to same color
// dp[i]
