#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
const ll oo = 1e18;
vector<tuple<int, int, int>> G[MAXN];
map<int, long long> mapa[MAXN];
map<int, long long> cost[MAXN][2];
void connect(int a, int b, int c, int h){
G[a].push_back({b, c, h});
G[b].push_back({a, c, h});
cost[a][0][c] = oo;
cost[a][1][c] = oo;
cost[b][0][c] = oo;
cost[b][1][c] = oo;
mapa[a][c];
mapa[b][c];
mapa[a][c] += h;
mapa[b][c] += h;
}
void dijkstra(){
priority_queue<tuple<long long, int, int, int, pair<int, int>>> Q;
Q.push({0, 1, 0, 0, {-1, 0}});
cost[1][0][0] = oo;
while(Q.size()){
auto [d, v, krawedz, plac, in] = Q.top();
Q.pop();
if(cost[v][plac][krawedz] <= -d) continue;
cost[v][plac][krawedz] = -d;
for(auto [u, c, h] : G[v]){
ll actcost;
//placimy za krawedz
actcost = h;
if(cost[u][1][c] > cost[v][plac][krawedz] + actcost)
Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 1, {c, h}});
//nie placimy za nia
actcost = mapa[v][c] - h;
if(c == in.first)
actcost = max(actcost - (ll)in.second, (ll)0);
if(cost[u][0][c] > cost[v][plac][krawedz] + actcost)
Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 0, {0, 0}});
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b, c, h;
cin >> a >> b >> c >> h;
connect(a, b, c, h);
}
dijkstra();
ll res = oo;
for(auto [u, c, h] : G[n])
res = min(res, min(cost[n][0][c], cost[n][1][c]));
if(res == oo)
res = -1;
cout << res << endl;
}
