#include <bits/stdc++.h>
using namespace std;
const int N = 202, M = 50004;
const long long INF = 1000000009000000009;
struct ban0
{
int x, y, c, d;
};
int n, m;
ban0 b[M];
struct ban
{
int x;
long long d;
int z;
int zn;
ban(){}
ban(int x, long long d, int z, int zn)
{
this->x = x;
this->d = d;
this->z = z;
this->zn = zn;
}
};
bool operator<(const ban& a, const ban& b)
{
return a.d > b.d;
}
vector<ban> a[N];
bool c[N][2][2];
long long djk()
{
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k)
c[i][j][k] = false;
priority_queue<ban> q;
q.push(ban(1, 0, 0, 0));
long long ans = INF;
while (1)
{
ban t;
do
{
if (q.empty())
{
return ans;
}
t = q.top();
q.pop();
} while (c[t.x][t.z][t.zn]);
c[t.x][t.z][t.zn] = true;
if (t.x == 1 && t.zn == 1)
ans = min(ans, t.d);
for (int i = 0; i < a[t.x].size(); ++i)
{
ban h = a[t.x][i];
if (t.z && h.z)
continue;
h.d += t.d;
h.z = (t.z | h.z);
h.zn = (t.zn | h.zn);
q.push(h);
}
}
}
void solv1()
{
long long ans = INF;
for (int j = 0; j <= m; ++j)
{
for (int i = 1; i <= n; ++i)
a[i].clear();
for (int i = 1; i <= m; ++i)
{
if (i == j)
{
if (b[i].x == n || b[i].y == n)
{
a[b[i].y].push_back(ban(b[i].x, b[i].c, 0, 1));
}
else
{
a[b[i].y].push_back(ban(b[i].x, b[i].c, 0, 0));
}
continue;
}
if (b[i].x == n || b[i].y == n)
{
a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 1));
}
else
{
a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 0));
}
}
if (j == 0)
ans = min(ans, djk());
else
ans = min(ans, djk() + b[j].d);
}
if (ans == INF)
printf("-1\n");
else
printf("%lld\n", ans);
}
void solv2()
{
for (int i = 1; i <= m; ++i)
{
if (b[i].x == n || b[i].y == n)
{
a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 1));
a[b[i].y].push_back(ban(b[i].x, b[i].c + b[i].d, 1, 1));
}
else
{
a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 0));
a[b[i].y].push_back(ban(b[i].x, b[i].c + b[i].d, 1, 0));
}
}
long long ans = djk();
if (ans == INF)
printf("-1\n");
else
printf("%lld\n", ans);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d%d", &b[i].x, &b[i].y, &b[i].c, &b[i].d);
}
solv1();
return 0;
}
