#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
#define int long long
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}
const int N = 1e5+5;
const ll INF = 1e18;
const int Mx = 2e5+1;
struct Node{
// color < Mx: some affect in color cost of that color
int v, cur_dist, color, dist_edge;
Node(int v = 0, int cur_dist = 0, int color = Mx): v(v), cur_dist(cur_dist), color(color) {}
bool operator < (const Node& q) const{
return cur_dist > q.cur_dist;
}
};
int n, m;
map<int,int> color_cost[N], dist[N];
map<int, vector<pair<int,int>>> adj[N];
void solve()
{
cin >> n >> m;
FOR(i, 1, m){
int u,v,c,w;
cin >> u >> v >> c >> w;
adj[u][c].push_back(make_pair(v, w));
adj[v][c].push_back(make_pair(u, w));
color_cost[u][c] += w;
color_cost[v][c] += w;
}
// 2 case: (choose to change u->v and affect v) && (choose to change u->v with no affect to v || choose to change all except u->v and no affect to v)
priority_queue<Node> pq;
pq.push(Node(1));
dist[1][Mx] = 0;
while(!pq.empty()){
Node eq = pq.top(); pq.pop();
int color = eq.color, x = eq.v;
if(dist[x][color] < eq.cur_dist) continue;
if(color < Mx){
int total = color_cost[x][color];
for(auto [v, w] : adj[x][color]){
// affect from x -> v, but don't keep affect
if(!dist[v].count(Mx) || ckmn(dist[v][Mx], dist[x][color] + total - w)){
dist[v][Mx] = dist[x][color] + total - w;
pq.push(Node(v, dist[v][Mx], Mx));
}
}
}
else{
for(auto [color, list_col] : adj[x]){
int total = color_cost[x][color];
for(auto [v, w] : list_col){
// don't affect v : change all except x->v or change only x->v
if(!dist[v].count(Mx) || ckmn(dist[v][Mx], dist[x][Mx] + total - w)){
dist[v][Mx] = dist[x][Mx] + total - w;
pq.push(Node(v, dist[v][Mx], Mx));
}
if(!dist[v].count(Mx) || ckmn(dist[v][Mx], dist[x][Mx] + w)){
dist[v][Mx] = dist[x][Mx] + w;
pq.push(Node(v, dist[v][Mx], Mx));
}
if(adj[v].count(color) && (int)adj[v][color].size() > 1){
// can affect
if(!dist[v].count(color) || ckmn(dist[v][color], dist[x][Mx])){
dist[v][color] = dist[x][Mx];
pq.push(Node(v, dist[v][color], color));
}
}
}
}
}
}
if(!dist[n].size()){
cout << "-1\n";
}
else{
cout << dist[n][Mx] <<"\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP","r",stdin);
freopen(name".OUT","w",stdout);
}
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}
