#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define siuuu "robot1"
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
int a[N];
map < ii , int > sum;
struct truc{
int l , r , c , p;
}edge[N];
vector< ii > g[N];
int dist[N];
int n , m;
int Time = n;
map < ii , int > mp;
int id(int u , int c){
if (mp[{u , c}]) return mp[{u , c}];
return mp[{u , c}] = ++Time;
}
void dijk(int ronaldo){
priority_queue< ii , vector< ii > , greater < ii > > q;
for (int i = 1 ; i <= Time ; i++) dist[i] = 1e18;
dist[ronaldo] = 0;
q.push({0 , ronaldo});
while (!q.empty()){
auto c = q.top();
q.pop();
int u = c.se , w = c.fi;
if (dist[u] < w) continue;
for (auto k : g[u]){
int v = k.fi , cost = k.se;
if (dist[v] > dist[u] + cost){
dist[v] = dist[u] + cost;
q.push({dist[v] , v});
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if(fopen(siuuu".inp","r"))
{
freopen(siuuu".inp","r", stdin);
freopen(siuuu".out","w", stdout);
}
cin >> n >> m;
Time = n;
for (int i = 1 ; i <= m ; i++){
int l , r , c , p;
cin >> l >> r >> c >> p;
edge[i] = {l , r , c , p};
sum[{l , c}] += p;
sum[{r , c}] += p;
}
for (int i = 1 ; i <= m ; i++){
auto [l , r , c , p] = edge[i];
int w_l = sum[{l , c}] - p;
int w_r = sum[{r , c}] - p;
w_l = min(w_l , p);
w_r = min(w_r , p);
g[l].push_back({r , w_l});
g[r].push_back({l , w_r});
// 4 dong k hieu
//
g[l].push_back({id(r , c) , 0});
g[id(r , c)].push_back({l , sum[{r , c}] - p});
g[r].push_back({id(l , c) , 0});
g[id(l , c)].push_back({r , sum[{l , c}] - p});
//
}
dijk(1);
cout << (dist[n] == 1e18 ? -1 : dist[n]);
return 0;
}
