#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;
// Trash code from https://www.geeksforgeeks.org/pairing-heap/
struct HeapNode {
pair<int, int> key;
HeapNode *leftChild;
HeapNode *nextSibling;
HeapNode():
leftChild(NULL), nextSibling(NULL) {}
// creates a new node
HeapNode(pair<int, int> key_, HeapNode *leftChild_, HeapNode *nextSibling_):
key(key_), leftChild(leftChild_), nextSibling(nextSibling_) {}
// Adds a child and sibling to the node
void addChild(HeapNode *node) {
if(leftChild == NULL)
leftChild = node;
else {
node->nextSibling = leftChild;
leftChild = node;
}
}
};
// Returns true if root of the tree
// is null otherwise returns false
bool Empty(HeapNode *node) {
return (node == NULL);
}
// Function to merge two heaps
HeapNode *Merge(HeapNode *A, HeapNode *B)
{
// If any of the two-nodes is null
// the return the not null node
if(A == NULL) return B;
if(B == NULL) return A;
// To maintain the min heap condition compare
// the nodes and node with minimum value become
// parent of the other node
if(A->key.first < B->key.first) {
A->addChild(B);
return A;
}
else {
B->addChild(A);
return B;
}
return NULL; // Unreachable
}
// Returns the root value of the heap
pair<int, int> Top(HeapNode *node) {
return node->key;
}
// Function to insert the new node in the heap
HeapNode *Insert(HeapNode *node, pair<int, int> key) {
return Merge(node, new HeapNode(key, NULL, NULL));
}
// This method is used when we want to delete root node
HeapNode *TwoPassMerge(HeapNode *node) {
if(node == NULL || node->nextSibling == NULL)
return node;
else {
HeapNode *A, *B, *newNode;
A = node;
B = node->nextSibling;
newNode = node->nextSibling->nextSibling;
A->nextSibling = NULL;
B->nextSibling = NULL;
return Merge(Merge(A, B), TwoPassMerge(newNode));
}
return NULL; // Unreachable
}
// Function to delete the root node in heap
HeapNode *Delete(HeapNode *node) {
return TwoPassMerge(node->leftChild);
}
struct PairingHeap {
HeapNode *root;
PairingHeap():
root(NULL) {}
bool Empty(void) {
return ::Empty(root);
}
pair<int, int> Top(void) {
return ::Top(root);
}
void Insert(pair<int, int> key) {
root = ::Insert(root, key);
}
void Delete(void) {
root = ::Delete(root);
}
void Join(PairingHeap other) {
root = ::Merge(root, other.root);
}
};
const int N = 200, M = 50000;
vector<int> graph[2][N];
int deg[N], rev_deg[N], path[N], dist[N], _from[M], _to[M], weight[M], cost[M];
int dist_w[4][M][N], dist_i[4][N];
int n, m;
int from(int g, int id) {
return g == 0 ? _from[id] : _to[id];
}
int to(int g, int id) {
return g == 0 ? _to[id] : _from[id];
}
void dijkstra(int start, int g, bool flag, int del = -1) {
fill(dist, dist + n, INT_MAX);
if (flag) fill(path, path + n, -1);
dist[start] = 0;
PairingHeap q;
q.Insert({0, start});
while (!q.Empty()) {
auto [d, u] = q.Top();
q.Delete();
if (dist[u] > d) {
continue;
}
for (int e : graph[g][u]) {
if (e != del && dist[u] + weight[e] < dist[to(g, e)]) {
dist[to(g, e)] = dist[u] + weight[e];
if (flag) path[to(g, e)] = e;
q.Insert({dist[to(g, e)], to(g, e)});
}
}
}
}
void _solve(int g, int start, int it) {
dijkstra(start, g, true);
memcpy(dist_i[it], dist, sizeof dist);
for (int i = 0; i < n; i++) {
if (path[i] != -1) {
dijkstra(start, g, false, path[i]);
memcpy(dist_w[it][path[i]], dist, sizeof dist);
}
}
}
int Get(int it, int id, int u) {
return dist_w[it][id][u] == -1 ? dist_i[it][u] : dist_w[it][id][u];
}
void solve() {
cin >> n >> m;
memset(dist_w, -1, sizeof dist_w);
for (int i = 0; i < m; i++) {
cin >> _from[i] >> _to[i] >> weight[i] >> cost[i];
_from[i]--, _to[i]--;
deg[_from[i]]++, rev_deg[_to[i]]++;
}
for (int i = 0; i < n; i++) {
graph[0][i].reserve(deg[i]);
graph[1][i].reserve(rev_deg[i]);
}
for (int i = 0; i < m; i++) {
graph[0][_from[i]].push_back(i);
graph[1][_to[i]].push_back(i);
}
_solve(0, 0, 0);
_solve(0, n - 1, 1);
_solve(1, 0, 2);
_solve(1, n - 1, 3);
int ans = INT_MAX;
if (dist_i[0][n - 1] != INT_MAX && dist_i[1][0] != INT_MAX) {
ans = dist_i[0][n - 1] + dist_i[1][0];
}
for (int u = 0; u < n; u++) {
for (int id : graph[0][u]) {
int AB = INT_MAX, BA = INT_MAX;
AB = min(AB, Get(0, id, n - 1));
if (Get(0, id, to(0, id)) != INT_MAX && Get(3, id, from(0, id)) != INT_MAX) {
AB = min(AB, Get(0, id, to(0, id)) + Get(3, id, from(0, id)) + weight[id]);
}
BA = min(BA, Get(1, id, 0));
if (Get(1, id, to(0, id)) != INT_MAX && Get(2, id, from(0, id)) != INT_MAX) {
BA = min(BA, Get(1, id, to(0, id)) + Get(2, id, from(0, id)) + weight[id]);
}
if (AB == INT_MAX || BA == INT_MAX) {
continue;
}
ans = min(ans, AB + BA + cost[id]);
}
}
cout << (ans == INT_MAX ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
