#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pb push_back
#define vec vector
#define um unordered_map
#define us unordered_set
#define ms multiset
#define cocainit ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define koconcainit return 0;
#define debug(x) cout << x << ' ';
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Forn(i, b, a) for(int i = b; i >= a; --i)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define MASK(i) (1 << (i))
#define BIT(i, x) (((x) >> (i)) & 1)
#define fileinp(x) freopen((x + ".inp").c_str(), "r", stdin)
#define fileout(x) freopen((x + ".out").c_str(), "w", stdout)
#define iiiiii iiiiii
const ll INF = (ll)4e18;
const int mx = 2e5 + 5;
const int mx2 = 5e5 + 5;
const int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const int MOD = 1e9 + 7;
const int MOD2 = 14062008;
struct edge{
int u,v,c;
ll w;
};
int s,k;
vec<edge> e;
vec<vec<pair<int,ll>>> a;
void dijkstra(){
vec<ll> d(s + 1, INF);
priority_queue<pair<ll,int>, vec<pair<ll,int>>, greater<pair<ll,int>>> pq;
d[1]=0;
pq.push({0, 1});
while(!pq.empty()){
auto [du,u] = pq.top(); pq.pop();
if(du!=d[u]) continue;
for(auto [v,w]:a[u]){
if(d[v] > du + w){
d[v] = du + w;
pq.push({d[v],v});
}
}
}
cout << (d[s] >= INF / 2 ? -1 : d[s]);
}
signed main(){
cocainit;
cin >> s >> k;
e.clear();
a.assign(s + 1,{});
For(i, 1, k){
int u,v,c; ll w;
cin >> u >> v >> c >> w;
e.pb({u, v, c, w});
}
vec<unordered_map<int,ll>> sum(s + 1);
for(auto &x: e){
sum[x.u][x.c] += x.w;
sum[x.v][x.c] += x.w;
}
for(auto &x:e){
ll su = sum[x.u][x.c];
ll sv = sum[x.v][x.c];
ll cu = min(x.w, su - x.w);
ll cv = min(x.w, sv - x.w);
a[x.u].pb({x.v, cu});
a[x.v].pb({x.u, cv});
}
dijkstra();
koconcainit;
}
