#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100001;
int n, m;
ll dist[mxN];
map<int, ll> trans[mxN];
map<int, ll> fdist[mxN];
vector<array<int, 3>> adj[mxN];
void solve() {
cin>>n>>m;
owo(i, 0, m) {
int a, b, c, d;
cin>>a>>b>>c>>d;
a--; b--;
adj[a].senpai({b, c, d});
adj[b].senpai({a, c, d});
trans[a][c]+=d;
trans[b][c]+=d;
fdist[a][c] = INFLL;
fdist[b][c] = INFLL;
}
memset(dist, INFLL, sizeof(dist));
dist[0] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 0});
while(!pq.empty()) {
auto[dx, u] = pq.top();
//cout<<dx<<" "<<u<<" "<<dist[u]<<endl;
pq.pop();
if(dx!=dist[u])continue;
for(auto v: adj[u]) {
//transition changing all but this edge
ll cost = min(dx, fdist[u][v[1]]) + trans[u][v[1]] - v[2];
cost = min(cost, dx + v[2]);
//cout<<u<<" "<<v[0]<<" "<<dx<<" "<<v[2]<<" "<<cost<<"\n";
if(cost < dist[v[0]]) {
dist[v[0]] = cost;
pq.push({cost, v[0]});
}
if(dx < fdist[v[0]][v[1]])fdist[v[0]][v[1]] = dx;
}
}
cout<<(dist[n-1]==INFLL ? -1 : dist[n-1])<<"\n";
}
int main() {
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
int T = 1;
for(int tc = 1; tc <= T; tc++) {
solve();
}
return 0;
}
