#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "JOI21_ho_t4"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 1e5 + 1;
const ll INF = 1e18;
int n, m;
using pi = pair<int, int>;
map<int, vector<pi>> adj[N];
map<int, ll> tot[N], dp2[N];
map<int, ll> dp[N];
using T = pair<ll, pair<int, int>>;
priority_queue<T, vector<T>, greater<T>> pq;
ll dijkstra(const int &s, const int &e){
FORU(i, 1, n) dp[i][0] = INF;
dp[e][0] = INF;
pq.emplace(0, mp(s, 0));
dp[s][0] = 0;
while(!pq.empty()){
ll wu = pq.top().fi;
auto [u, cu] = pq.top().se;
pq.pop();
if(cu){
if(dp2[u][cu] != wu) continue;
for(auto [v, wv]: adj[u][cu]){
ll w = wu + (tot[u][cu] - wv);
if(dp[v][0] > w){
dp[v][0] = w;
pq.emplace(dp[v][0], mp(v, 0));
}
}
} else{
if(dp[u][0] != wu) continue;
for(auto [cv, ed]: adj[u]){
for(auto [v, wv]: ed){
ll case1 = wu + wv;
if(!dp[v].count(0) || dp[v][0] > case1){
dp[v][0] = case1;
pq.emplace(dp[v][0], mp(v, 0));
}
ll case2 = wu + (tot[u][cv] - wv);
if(!dp[v].count(0) || dp[v][0] > case2){
dp[v][0] = case2;
pq.emplace(dp[v][0], mp(v, 0));
}
ll case3 = wu;
if(!dp2[v].count(cv) || dp2[v][cv] > case3){
dp2[v][cv] = case3;
pq.emplace(dp2[v][cv], mp(v, cv));
}
}
}
}
}
return (dp[e][0] == INF ? -1 : dp[e][0]);
}
int main(){
IOS;
Fi();
cin >> n >> m;
FORU(i, 1, m){
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u][c].eb(v, p);
adj[v][c].eb(u, p);
tot[u][c] += p;
tot[v][c] += p;
}
cout << dijkstra(1, n);
return 0;
}
