#include<bits/stdc++.h> #define M 100005 usingnamespacestd; typedeflonglong ll;
template<typename T> inlinevoidread(T &num){ T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
const ll inf = 1e16; int n, m; int head[205][2], lst[205][2], from[M][2], pre[M][2], to[M][2], sz[2]; //0:原图 1:反图 ll c[M][2], d[M][2], ans, mn[M][2]; bool ok[M][2];
priority_queue<pair<ll, int> > q; ll dis[205][2], tmp[205]; bool vis[205], tag[M][2]; voiddijkstra(int s, int tp){ for (int i = 1; i <= n; i++) dis[i][tp] = inf; dis[s][tp] = 0; memset(vis, 0, sizeof(vis)); q.push(make_pair(0, s)); while (!q.empty()) { int x = q.top().second; q.pop(); if (vis[x]) continue; vis[x] = 1; for (int i = head[x][tp]; i; i = pre[i][tp]) { int y = to[i][tp]; if (dis[y][tp] > dis[x][tp] + c[i][tp]) { dis[y][tp] = dis[x][tp] + c[i][tp]; lst[y][tp] = i; q.push(make_pair(-dis[y][tp], y)); } } } }
voidtmp_dij(int s, int tp){ for (int i = 1; i <= n; i++) tmp[i] = inf; tmp[s] = 0; memset(vis, 0, sizeof(vis)); q.push(make_pair(0, s)); while (!q.empty()) { int x = q.top().second; q.pop(); if (vis[x]) continue; vis[x] = 1; for (int i = head[x][tp]; i; i = pre[i][tp]) { int y = to[i][tp]; if (!ok[i][tp]) continue; if (tmp[y] > tmp[x] + c[i][tp]) { tmp[y] = tmp[x] + c[i][tp]; q.push(make_pair(-tmp[y], y)); } } } }
voidsolve(int s, int t, int o){ dijkstra(s, 0); dijkstra(t, 1); memset(tag, 0, sizeof(tag)); for (int i = 1; i <= n; i++) { tag[lst[i][0]][0] = 1; tag[lst[i][1]][0] = 1; } for (int i = 1; i <= sz[0]; i++) { int u = from[i][0], v = to[i][0]; ll now = c[i][0]; if (!tag[i][0]) { mn[i][o] = dis[t][0]; now += dis[v][0]; } else { ok[i][0] = 0; tmp_dij(s, 0); ok[i][0] = 1; mn[i][o] = tmp[t]; now += tmp[v]; } if (!tag[i][1]) { now += dis[u][1]; } else { ok[i][1] = 0; tmp_dij(t, 1); ok[i][1] = 1; now += tmp[u]; } mn[i][o] = min(mn[i][o], now); } }
intmain(){ read(n); read(m); for (int i = 1, u, v; i <= m; i++) { ll cc, dd; read(u); read(v); read(cc); read(dd); addedge(u, v, cc, dd, 0); addedge(v, u, cc, dd, 1); } ans = inf; ll now = 0; dijkstra(1, 0); now += dis[n][0]; dijkstra(n, 0); now += dis[1][0]; ans = min(ans, now); solve(1, n, 0); solve(n, 1, 1); for (int i = 1; i <= sz[0]; i++) { ans = min(ans, mn[i][0] + mn[i][1] + d[i][0]); } printf("%lld\n", ans >= inf ? -1 : ans); return0; }