#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(name)){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
const int maxn = 1e5+10;
const int INF = 1e9;
int n,m;
struct Edge{
int to, color, price, id;
};
vector<Edge> adj[maxn];
vector<pi> adj2[maxn];
int main(){
setIO();
cin>>n>>m;
vector<pair<pi, pi>> edges(m);
for (int i = 0; i < m; i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
a--; b--;
adj[a].pb({b, c, d, i});
adj[b].pb({a, c, d, i});
edges[i] = {{a,b}, {c,d}};
}
//you don't have to change all of them if you only want to take 1 path
for (int i = 0; i < n; i++){
vi idx[m];
for (auto j : adj[i]){
idx[j.color].pb(j.id);
}
for (int j = 0; j < m; j++){
if (idx[j].size() > 1){
for (auto k : idx[j]){
pair<pi, pi> edge = edges[k];
int x = edge.first.first, y = edge.first.second;
int weight = edge.second.second;
if (y == i){
swap(x,y);
}
adj2[x].pb({y, weight});
}
}
}
}
vi dist(n, INF);
dist[0] = 0;
priority_queue<pi, vector<pi>, greater<pi>> pq;
pq.push({0,0});
while (pq.size()){
auto [d, node] = pq.top();
pq.pop();
if (d > dist[node]){
continue;
}
for (auto i : adj2[node]){
if (dist[i.first] > dist[node] + i.second){
dist[i.first] = dist[node] + i.second;
pq.push({dist[i.first], i.first});
}
}
}
if (dist[n-1] == INF){
cout<<-1<<endl;
} else {
cout<<dist[n-1]<<endl;
}
}
