#include <bits/stdc++.h>
#define ull unsigned long long
#define db double
#define fi first
#define se second
#define PB push_back
#define EB emplace_back
#define ll long long
#define int long long // consider carefully
#define pii pair<int, int>
#define pli pair<ll, int>
// TIME IS LIMITED ...
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, b, a) for (int i = (b); i >= (a); --i)
#define repv(v, H) for(auto &v: H)
#define FOR rep
#define FORD repd
// REFLECT ON THE PAST ...
#define FORV(v, H) for(auto &v: H)
#define reset(c, x) memset(c, x, sizeof(c))
#define FULL(i) (1LL << (i))
#define BIT(mask, i) ((mask >> i) & 1)
#define ONBIT(mask, i) (mask (1LL << (i)))
#define OFFBIT(mask, i) (mask &~ (1LL << (i)))
#define REV(mask, i) (mask ^ (1LL << (i)))
#define COUNTBIT __builtin_popcountll
#define lwb lower_bound
#define upb upper_bound
#define ALL(v) v.begin(), v.end()
#define SE(v) ((int) v.size())
#define special(v) v.erase(unique(ALL(v)), v.end())
#define sp ' '
#define nl '\n'
#define yes "YES"
#define no "NO"
#define Lg2(n) (63 - __builtin_clzll(n))
#define left __left
#define right __right
#define lef(id) (id << 1)
#define rig(id) ((id << 1) | 1)
using namespace std;
template <class X, class Y> bool maximize(X &a, const Y &b) {
if(a < b) return a = b, true;
return false;
}
template <class X, class Y> bool minimize(X &a, const Y &b) {
if(a > b) return a = b, true;
return false;
}
//template <class... T>
//void print(T&&... n) {
// using exp = int[];
// exp{0, (cerr << n << sp, 0)...};
// cerr << endl;
//}
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
const long long oo = 1e18 + 7;
const int INF = INT_MAX;
const int MAX = 1e5 + 7;
const int MOD = 1e9 + 7;
const int MAXV = 1e6 + 7;
const int base = 311;
/****************************/
// 3, 2, 1, STARTTT, CODEE !!
int N, M;
struct Edge {
int u, v, c, w;
} ee[MAX << 1];
struct Data {
int x1, x2, x3, x4;
Data(int _x1 = 0, int _x2 = 0, int _x3 = 0, int _x4 = 0) : x1(_x1), x2(_x2), x3(_x3), x4(_x4) {}
bool operator < (const Data &ot) const {
return x2 <= ot.x2;
}
};
vector<Data> G[MAX];
namespace subtask1 {
static const int MAX = 1e3 + 10;
ll d[MAX][2][MAX << 1];
struct panda {
ll dd;
int v, t, id;
panda(ll _dd = 0, int _v = 0, int _t = 0, int _id = 0) :
dd(_dd), v(_v), t(_t), id(_id) {}
bool operator < (const panda &ot) const {
return dd > ot.dd;
}
};
void SOLVE() {
vector<vector<ll>> sum(N + 5, vector<ll>(M + 5, 0));
rep(u, 1, N) {
repv(e, G[u]) {
int v = e.x1;
int c = e.x2;
int w = e.x3;
int id = e.x4;
sum[u][c] += w;
}
}
priority_queue<panda> pq;
rep(i, 1, N) {
rep(j, 0, M) rep(t, 0, 1) d[i][t][j] = oo;
}
d[1][0][0] = 0;
pq.push(panda(0, 1, 0, 0));
while(!pq.empty()) {
auto cur = pq.top();
pq.pop();
ll du = cur.dd;
int u = cur.v;
int t = cur.t;
int id = cur.id;
if(du != d[u][t][id]) continue;
int prew = ee[id].w;
int c = ee[id].c;
repv(e, G[u]) {
int v = e.x1;
int c2 = e.x2;
int w = e.x3;
int id2 = e.x4;
if(id2 == id) continue;
// print(v, c2, w, id2);
bool ok = sum[u][c] > 0;
if(ok) sum[u][c] -= prew * t;
ll new_w = min((ll) w, sum[u][c2] - w);
int t2 = w <= sum[u][c2] ? 1 : 0;
if(d[v][t2][id2] > du + new_w) {
d[v][t2][id2] = du + new_w;
pq.push(panda(du + new_w, v, t2, id2));
}
if(ok) sum[u][c] += prew * t;
}
}
ll ans = oo;
rep(j, 1, M) rep(t, 0, 1) {
minimize(ans, d[N][t][j]);
}
cout << (ans == oo ? -1 : ans) << nl;
}
}
namespace subtask2 {
// static const int MAX = 1e3 + 10;
map<int, ll> d[MAX][2];
map<int, ll> sum[MAX];
struct panda {
ll dd;
int v, t, id;
panda(ll _dd = 0, int _v = 0, int _t = 0, int _id = 0) :
dd(_dd), v(_v), t(_t), id(_id) {}
bool operator < (const panda &ot) const {
return dd > ot.dd;
}
};
void SOLVE() {
rep(u, 1, N) {
repv(e, G[u]) {
int v = e.x1;
int c = e.x2;
int w = e.x3;
int id = e.x4;
sum[u][c] += w;
}
}
priority_queue<panda> pq;
d[1][0][0] = 0;
pq.push(panda(0, 1, 0, 0));
while(!pq.empty()) {
auto cur = pq.top();
pq.pop();
ll du = cur.dd;
int u = cur.v;
int t = cur.t;
int id = cur.id;
if(du != d[u][t][id]) continue;
int prew = ee[id].w;
int c = ee[id].c;
repv(e, G[u]) {
int v = e.x1;
int c2 = e.x2;
int w = e.x3;
int id2 = e.x4;
if(id2 == id) continue;
// print(v, c2, w, id2);
bool ok = sum[u].count(c) > 0;
if(ok) sum[u][c] -= prew * t;
ll new_w = min((ll) w, sum[u][c2] - w);
int t2 = w <= sum[u][c2] ? 1 : 0;
if(d[v][t2].count(id2) == 0 || d[v][t2][id2] > du + new_w) {
d[v][t2][id2] = du + new_w;
pq.push(panda(du + new_w, v, t2, id2));
}
if(ok) sum[u][c] += prew * t;
}
}
ll ans = oo;
rep(t, 0, 1) {
repv(pa, d[N][t]) {
minimize(ans, pa.se);
}
}
cout << (ans == oo ? -1 : ans) << nl;
}
}
namespace subtask3 {
void SOLVE() {
vll sum(N + 5, 0);
vector<vector<pair<ll, int>>> G2(N + 2 * M + 10, vector<pair<ll, int>>());
int dem = N;
rep(u, 1, N) {
repv(e, G[u]) {
int c = e.x2;
int w = e.x3;
sum[c] += w;
}
sort(ALL(G[u]));
int last = 0;
repv(e, G[u]) {
int v = e.x1;
int c = e.x2;
int w = e.x3;
if(c != last) {
last = c;
++dem;
G2[u].emplace_back(0, dem);
}
G2[v].emplace_back(sum[c] - w, dem);
G2[dem].emplace_back(sum[c] - w, v);
G2[u].emplace_back(w, v);
G2[v].emplace_back(w, u);
}
repv(e, G[u]) {
int c = e.x2;
int w = e.x3;
sum[c] -= w;
}
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
vll d(dem + 5, oo);
d[1] = 0;
pq.emplace(0, 1);
while(!pq.empty()) {
auto cur = pq.top();
pq.pop();
int u = cur.se;
ll du = cur.fi;
if(d[u] != du) continue;
repv(e, G2[u]) {
int v = e.se;
ll w = e.fi;
if(minimize(d[v], d[u] + w)) {
pq.emplace(d[v], v);
}
}
}
ll ans = d[N];
cout << (ans == oo ? -1 : ans) << nl;
}
}
void roxie() {
cin >> N >> M;
rep(i, 1, M) {
int u, v, c, w;
cin >> u >> v >> c >> w;
ee[i] = {u, v, c, w};
G[u].push_back(Data(v, c, w, i));
G[v].push_back(Data(u, c, w, i));
}
if(N <= 1000 && M <= 2000)
subtask1:: SOLVE();
else
subtask2:: SOLVE();
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string task = "robot1";
if(fopen((task + ".inp").c_str(), "r")) {
freopen((task + ".inp").c_str(), "r", stdin);
freopen((task + ".out").c_str(), "w", stdout);
}
int test = 1;
// cin >> test;
while(test--) {
roxie();
}
cerr << nl << "run in: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s" << nl << nl;
return 0;
}
