#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int,int,int> ti;
#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int INF = 1<<30;
int N,M,V[MAXN], D[MAXN];
vector<ti> edges[MAXN];
map<int, int> cc[MAXN];
bool dfs(int curr, int dest){
V[curr] = 1;
if(curr == dest) return true;
bool res = false;
for(auto e : edges[curr]){
if(!V[get<0>(e)]) res |= dfs(get<0>(e), dest);
}
return res;
}
void djikstras(int src){
priority_queue<pi, vector<pi>, greater<pi>> pq;
fill(begin(D), end(D), INF);
pq.push({D[src] = 0, src});
while(!pq.empty()){
int cdist, node;
tie(cdist, node) = pq.top(); pq.pop();
if(cdist != D[node]) continue;
if(node == N) break;
for(auto e : edges[node]){
int cost = min(get<2>(e), cc[node][get<1>(e)] - get<2>(e));
if(cdist + cost < D[get<0>(e)]){
pq.push({D[get<0>(e)] = cdist + cost, get<0>(e)});
}
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
for(int i = 0; i < M; i++){
int ai, bi, ci, pi;
cin >> ai >> bi >> ci >> pi;
edges[ai].push_back({bi, ci, pi});
edges[bi].push_back({ai, ci, pi});
if(cc[ai].find(ci) != cc[ai].end()){
cc[ai][ci] += pi;
cc[bi][ci] += pi;
}else{
cc[ai][ci] = pi;
cc[bi][ci] = pi;
}
}
if(!dfs(1, N)){
cout << "-1\n";
exit(0);
}
djikstras(1);
cout << D[N] << "\n";
}
