#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
using namespace std;
template<class T> using V = vector<T>;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = V<int>;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)((x).size())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i,n) for (int i = 1; i <= (int)(n); ++i)
#define forr(i,a,b) for (int i = (a); i <= (int)(b); ++i)
#define rfor(i,a,b) for (int i = (a); i >= (int)(b); --i)
const ll INF64 = (1LL<<62) - 1;
const int INF = 0x3f3f3f3f;
const int MOD = 1'000'000'007;
struct FastIO {
FastIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(std::ios::fixed); cout.precision(12);
}
} fastio;
inline void setIO(const string& inFile, const string& outFile){
if (!inFile.empty()) assert(freopen(inFile.c_str(), "r", stdin) != nullptr);
if (!outFile.empty()) assert(freopen(outFile.c_str(), "w", stdout) != nullptr);
}
inline void setIO(const string& base){
setIO(base + ".in", base + ".out");
}
template <class T, class U>
struct PairHash {
std::size_t operator()(const std::pair<T, U>& p) const noexcept {
std::size_t h1 = std::hash<T>{}(p.first);
std::size_t h2 = std::hash<U>{}(p.second);
return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
}
};
template<class T> inline bool chmin(T& a, const T& b){ if(b < a){ a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, const T& b){ if(a < b){ a = b; return true; } return false; }
template<class T> inline T ceil_div(T a, T b){
return (a>=0 ? (a + b - 1)/b : a/b);
}
template<class T> inline T floor_div(T a, T b){
return (a>=0 ? a/b : (a - b + 1)/b);
}
template<class T> inline T clampv(T x, T lo, T hi){ return x < lo ? lo : (x > hi ? hi : x); }
template<class T> string to_str(const T& x){ std::ostringstream os; os << x; return os.str(); }
ll modpow(ll a, ll e, ll m=MOD){
ll r = 1; a %= m; while(e){ if(e&1) r = (__int128)r*a % m; a = (__int128)a*a % m; e >>= 1; }
return r;
}
template<class T>
vector<int> compress(const vector<T>& a, vector<T>* values_out=nullptr){
vector<T> v = a; sort(all(v)); v.erase(unique(all(v)), v.end());
if(values_out) *values_out = v;
vector<int> id(a.size());
rep(i, a.size()) id[i] = (int)(lower_bound(all(v), a[i]) - v.begin());
return id;
}
template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto& x : v) is >> x; return is; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v){
for (int i = 0; i < sz(v); ++i) os << v[i] << (i+1==sz(v) ? "" : " ");
return os;
}
struct DSU {
V<int> e; void init(int N) { e = V<int>(N,-1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x), y = get(y); if (x == y) return 0;
if (e[x] > e[y]) swap(x,y);
e[x] += e[y]; e[y] = x; return 1;
}
};
const int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1}, dy8[8] = {0,1,1,1,0,-1,-1,-1};
const int kx[8] = {1,2,2,1,-1,-2,-2,-1}, ky[8] = {2,1,-1,-2,-2,-1,1,2};
struct edge{
int dest, color, cost;
bool operator>(edge other) const {
return cost > other.cost;
}
};
int main(){
int N, M;
cin >> N >> M;
V<V<edge>> adj(N);
rep(i, M){
int a, b, c, p;
cin >> a >> b >> c >> p;
a--, b--;
adj[a].pb({b, c, p});
adj[b].pb({a, c, p});
}
priority_queue<edge, vector<edge>, greater<edge>> q;
q.push({0, 0, 0});
vi dist(N, -1);
while(!q.empty()){
auto f = q.top();
q.pop();
if(dist[f.dest] != -1) continue;
//cout << "visiting: " << f.dest << ", cost: " << f.cost << endl;
//increment cost later
dist[f.dest] = f.cost;
//iterate over each thing, check how many have each color
//if >1 have some color, check if cheaper to change that or change everything else, then perform and continue
//keeps count, sum
unordered_map<int, pii> colors;
for(edge& e: adj[f.dest]){
colors.try_emplace(e.color, 0, 0);
colors[e.color].first++;
colors[e.color].second += e.cost;
}
for(edge& e: adj[f.dest]){
if(colors[e.color].first == 1) q.push({e.dest, e.color, f.cost});
//more than one of this color
else{
//if cost exceeds sum-this, pay sum-this
q.push({e.dest, e.color, f.cost+min(e.cost, colors[e.color].second-e.cost)});
}
}
}
cout << dist[N-1] << endl;
}
