#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int maxN = 100'000;
const long long INF = 1'000'000'000'000'000'000LL;
vector<int> edge[1+maxN];
vector<long long> dist[1+maxN];
void addEdge(int u, int v, long long w)
{
edge[u].push_back(v);
dist[u].push_back(w);
}
struct col
{
int c;
int o;
};
bool operator < (col A, col B)
{
return A.c < B.c;
}
set<col> cols[1+maxN];
void addCol(int u, int c)
{
set<col>::iterator it = cols[u].find(col{c, -1});
if(it == cols[u].end())
cols[u].insert(col{c, 1});
else
{
int o = it->o + 1;
cols[u].erase(it);
cols[u].insert(col{c, o});
}
}
vector<long long> dist1(1+maxN, INF);
struct pos
{
int u;
};
bool operator < (pos A, pos B)
{
if(dist1[A.u] == dist1[B.u])
return A.u < B.u;
else
return dist1[A.u] < dist1[B.u];
}
int main()
{
int N, M;
cin >> N >> M;
//color, change cost
int A[M+1], B[M+1], C[M+1], P[M+1];
for(int j = 1; j <= M; j++)
{
cin >> A[j] >> B[j] >> C[j] >> P[j];
addCol(A[j], C[j]);
addCol(B[j], C[j]);
}
for(int j = 1; j <= M; j++)
{
if(cols[ A[j] ].find(col{C[j], -1})->o == 1)
addEdge(A[j], B[j], 0);
else
addEdge(A[j], B[j], P[j]);
if(cols[ B[j] ].find(col{C[j], -1})->o == 1)
addEdge(B[j], A[j], 0);
else
addEdge(B[j], A[j], P[j]);
}
dist1[1] = 0;
set<pos> tbv;
for(int i = 1; i <= N; i++) tbv.insert(pos{i});
while(!tbv.empty())
{
int u = tbv.begin()->u;
tbv.erase(tbv.begin());
for(int e = 0; e < edge[u].size(); e++)
{
int v = edge[u][e];
long long w = dist[u][e];
if(dist1[u] + w < dist1[v])
{
tbv.erase(pos{v});
dist1[v] = dist1[u] + w;
tbv.insert(pos{v});
}
}
}
if(dist1[N] >= INF)
dist1[N] = -1;
cout << dist1[N] << '\n';
}
