#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define N 100005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, m;
int a[N], c[N];
vector<ii>g[N];
namespace sub1
{
const int M1 = 1005, M2 = 2005;
ll d[M1], sum[M2][M2];
struct trip
{
int w, node, color, idx;
};
struct cmp
{
bool operator()(trip a, trip b)
{
return a.w > b.w;
}
};
void bfs()
{
for(int i = 1; i <= n; i++)
d[i] = 1e18;
priority_queue<trip, vector<trip>, cmp>q;
q.push({0, 1, 0, 0});
d[1] = 0;
while(q.empty() != 1)
{
trip top = q.top();
q.pop();
int kc = top.w, u = top.node, color = top.color, idx1 = top.idx;
for(ii i : g[u])
{
int v = i.F, idx2 = i.S;
sum[u][color] += c[idx1];
sum[u][a[idx1]] -= c[idx1];
for(int j = 1; j <= m; j++)
{
if(a[idx2] == j)
{
if(d[v] > kc + sum[u][j] - c[idx2])
{
d[v] = kc + sum[u][j] - c[idx2];
q.push({d[v], v, j, idx2});
}
}
else if(d[v] > kc + sum[u][j] + c[idx2])
{
d[v] = kc + sum[u][j] + c[idx2];
q.push({d[v], v, j, idx2});
}
}
sum[u][color] -= c[idx1];
sum[u][a[idx1]] += c[idx1];
}
}
}
void deb()
{
cout<<endl;
for(int i=1;i<=n;i++)
cout<<i<<": "<<d[i]<<"\n";
cout<<endl;
}
void solve()
{
for(int i = 1; i <= n; i++)
for(ii j : g[i])
{
int idx = j.S;
sum[i][a[idx]] += c[idx];
}
bfs();
// deb();
cout << (d[n] == 1e18 ? -1 : d[n]);
}
}
namespace sub2
{
void solve()
{
}
}
main()
{
// freopen("BAI2.inp","r",stdin);
// freopen("BAI2.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y, z, w;
cin >> x >> y >> z >> w;
a[i] = z;
c[i] = w;
g[x].push_back({y, i});
g[y].push_back({x, i});
}
if(n <= 1000 && m <= 2000)
sub1::solve();
else
sub2::solve();
}
/**
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
5 2
1 4 1 2
3 5 1 4
5 6
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 2
3 5 2 2
4 5 3 4
= 3
5 6
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 5
3 5 2 2
4 5 3 4
=3
5 6
1 2 1 1
1 3 1 3
2 4 2 5
3 2 3 5
3 5 2 2
4 5 3 4
=1
5 7
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 5
3 5 2 2
4 5 3 4
3 4 1 3
5 8
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 5
3 5 2 2
4 5 3 4
3 4 1 3
2 5 3 4
**/
