#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true; return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
using ll = long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }
const int MAX = 2e5 + 5;
struct DisjointSet{
vector<int> lab;
DisjointSet(int n) : lab(n, -1) {}
int root(int u){
return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}
bool unite(int u, int v){
u = root(u);
v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
bool same_set(int u, int v){
return root(u) == root(v);
}
};
int n, m;
map<int, vector<pair<int, int>>> adj[MAX];
map<int, ll> same_color_sum[MAX];
ll dp[MAX];
map<int, ll> dp_last[MAX];
void testcase(){
cin >> n >> m;
DisjointSet dsu(n + 1);
while(m--){
int u, v, c, p;
cin >> u >> v >> c >> p;
dsu.unite(u, v);
adj[u][c].push_back({v, p});
adj[v][c].push_back({u, p});
same_color_sum[u][c] += p;
same_color_sum[v][c] += p;
// cout << u << " " << c << " " << p << '\n';
// cout << v << " " << c << " " << p << '\n';
}
if(!dsu.same_set(1, n)){
cout << -1 << '\n';
return;
}
memset(dp, 0x3f, sizeof(dp));
priority_queue<tuple<ll, int, int>> pq;
pq.push({-(dp[1] = 0), 1, 0});
while(!pq.empty()){
ll mincost; int u, c;
tie(mincost, u, c) = pq.top(); pq.pop();
mincost *= -1;
// cout << dbg(u) << dbg(c) << dbg(mincost) << '\n';
if(c == 0){
if(mincost != dp[u]) continue;
//last edge color does not matter
for(auto [c, vec] : adj[u]){
ll tot = same_color_sum[u][c];
for(auto [v, w] : vec){
ll change_neighbours = dp[u] + tot - w;
if(minimize(dp[v], change_neighbours)){
// cout << dbg(v) << dbg(change_neighbours) << '\n';
pq.push({-dp[v], v, 0}); //we can consider this edge as color 0 because it never goes back same edge
}
ll change_current = dp[u] + w;
if(minimize(dp[v], change_current)){
// cout << dbg(v) << dbg(change_current) << '\n';
pq.push({-dp[v], v, 0}); //as same as above
}
ll keep = dp[u];
if(dp_last[v].find(c) == dp_last[v].end() || dp_last[v][c] > keep){
dp_last[v][c] = keep;
pq.push({-keep, v, c});
}
}
}
} else{
ll correct = dp_last[u][c];
if(mincost != correct) continue;
ll tot = same_color_sum[u][c];
for(auto [v, w] : adj[u][c]){
ll change_neighbours = mincost + tot - w;
if(minimize(dp[v], change_neighbours)){
pq.push({-dp[v], v, 0}); //consider same cases
}
}
}
}
ll ans = dp[n];
cout << ans << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#define filename "task"
if(fopen(filename".inp", "r")){
freopen(filename".inp", "r", stdin);
freopen(filename".out", "w", stdout);
}
int T = 1; //cin >> T;
while(T--) testcase();
return 0;
}
