#include <bits/stdc++.h>
#define name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int n, m;
struct dl{
ll h;
int a, b, c;
bool operator < (const dl &o) const {return h > o.h;}
};
vector <dl> g[maxn];
ll cost[1003][2003], dp[1003][2003];
void sub1(){
fi(i, 1, n)
fi(j, 0, m) dp[i][j] = 1e18;
priority_queue <dl> q;
dp[1][0] = 0;
q.push({0, 1, 0, 0});
while(q.size()){
auto [h, u, x, y] = q.top(); q.pop();
if(h != dp[u][x]) continue;
fi(i, 1, m){
for(auto [v, cl, p, id]: g[u]){
int tmp = 0;
if(cl == x) tmp = y;
if(dp[v][cl] > h + cost[u][cl] - p + tmp){
dp[v][cl] = h + cost[u][cl] - p + tmp;
q.push({dp[v][cl], v, cl, p});
}
if(dp[v][0] > h + p){
dp[v][0] = h + p;
q.push({dp[v][0], v, 0, p});
}
}
}
}
ll res = 1e18;
fi(i, 0, m) res = min(res, dp[n][i]);
if(res != 1e18) cout << res;
else cout << -1;
exit(0);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// freopen(name".in", "r", stdin);
// freopen(name".out", "w", stdout);
cin >> n >> m;
fi(i, 1, m){
int u, v, c, p; cin >> u >> v >> c >> p;
g[u].pb({v, c, p, i});
g[v].pb({u, c, p, i});
cost[u][c] += p;
cost[v][c] += p;
}
if(n <= 1000 && m <= 2000) sub1();
}
