#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){
using tip = tuple<int, int, pair<int, int>>;
priority_queue<tip, vector<tip>, greater<tip>> pq;
fill(begin(D), end(D), INF);
fill(begin(V), end(V), 0);
pq.push({D[src] = 0, src, {0,0}});
while(!pq.empty()){
int cdist, node;
pi update;
tie(cdist, node, update) = pq.top(); pq.pop();
if(cdist != D[node] && update == make_pair(0,0)) continue;
D("%d (%d)\n", node, cdist);
V[node] = 1;
cc[node][update.first] -= update.second;
for(auto e : edges[node]){
if(V[get<0>(e)]) continue;
D("Node: %d, Colour: %d, cost: %d\n", node, get<1>(e), cc[node][get<1>(e)]);
int cost = min(get<2>(e), cc[node][get<1>(e)] - get<2>(e));
if(cdist + cost < D[get<0>(e)]){
D("pushing: {%d, %d}\n", cdist+cost, get<0>(e));
pi nu = (get<2>(e) < cc[node][get<1>(e)] - get<2>(e)) ? make_pair(get<1>(e), get<2>(e)) : make_pair(0,0);
pq.push({D[get<0>(e)] = cdist + cost, get<0>(e), nu});
}
}
cc[node][update.first] += update.second;
}
}
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";
}else{
djikstras(1);
cout << D[N] << "\n";
}
}
