#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
int n,m;
int a,b,c,p;
struct edge{
int target,c,p;
};
vector<edge> grph[100069];
set<int> grphcol[100069];
set<int> dupcol[100069];
bool done[100069];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for (int i = 0; i < m; i++) {
cin>>a>>b>>c>>p;
a--;b--;
grph[a].push_back({b,c,p});
grph[b].push_back({a,c,p});
if (grphcol[a].find(c)!=grphcol[a].end()) {
if (dupcol[a].find(c)==dupcol[a].end()) {
dupcol[a].insert(c);
}
}
else{
grphcol[a].insert(c);
}
if (grphcol[b].find(c)!=grphcol[b].end()) {
if (dupcol[b].find(c)==dupcol[b].end()) {
dupcol[b].insert(c);
}
}
else{
grphcol[b].insert(c);
}
}
pq.push({0,0});
while (pq.size()) {
auto temp=pq.top();
pq.pop();
if (done[temp.s]) {
continue;
}
done[temp.s]=true;
if (temp.s==n-1) {
cout<<temp.f<<endl;
return 0;
}
for (auto i:grph[temp.s]) {
if (dupcol[temp.s].find(i.c)==dupcol[temp.s].end()) {
pq.push({temp.f,i.target});
}
else{
pq.push({temp.f+i.p,i.target});
}
}
}
cout<<"-1"<<endl;
return 0;
}
