#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
int n, m;
vector<ar<int, 3>> input[MAXN];
vector<ar<int, 2>> adj[MAXN];
map<int, ll> sum[MAXN];
ll dist[MAXN];
void solve() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c, p; cin >> a >> b >> c >> p, --a, --b, --c;
input[a].push_back({b, c, p}), input[b].push_back({a, c, p});
sum[a][c] += p, sum[b][c] += p;
}
for (int a = 0; a < n; a++) {
for (auto [b, c, p] : input[a]) {
int cost = min((long long) p, sum[a][c] - p);
adj[a].push_back({b, cost});
}
dist[a] = INF;
}
min_pq<pair<ll, int>> q; q.push({0, 0});
dist[0] = 0;
while (sz(q)) {
auto [d, c] = q.top(); q.pop();
if (d != dist[c]) continue;
for (auto [nxt, w] : adj[c]) if (dist[nxt] > dist[c] + w) {
dist[nxt] = dist[c] + w;
q.push({dist[nxt], nxt});
}
}
ll ans = dist[n-1];
if (ans == INF) ans = -1;
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int T=1;
// cin >> T;
while (T--) solve();
}
