#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 100000;
map <int, ll> dist[N+5];
map <int, ll> cost[N+5];
vector <pair <int, int>> graf[N+5];
const ll INF = 1000000000000000000LL;
const int M = 200000;
ll edg[M+5];
int clr[M+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
for(int i=1; i<=n; i++){
dist[i][0] = INF;
}
for(int i=1; i<=m; i++){
int a, b, c, p;
cin >> a >> b >> c >> p;
graf[a].push_back({b, i});
graf[b].push_back({a, i});
dist[b][i] = INF;
dist[a][i] = INF;
cost[a][c] += p;
cost[b][c] += p;
edg[i] = p;
clr[i] = c;
}
dist[1][0] = 0;
set <pair <ll, pair <int, int>>> q;
q.insert({0, {1, 0}});
while(!q.empty()){
pair <int, int> prr = q.begin()->second;
q.erase(q.begin());
int v = prr.first;
int od = prr.second;
ll dst = dist[v][od];
for(auto tp : graf[v]){
int c = tp.first;
int koja = tp.second;
int col = clr[koja];
ll sve = cost[v][col] - edg[koja];
if(od && clr[od] == col) sve -= edg[od];
/// bojim tu
ll nd = dst + edg[koja];
if(dist[c][koja] > nd){
q.erase({dist[c][koja], {c, koja}});
dist[c][koja] = nd;
q.insert({dist[c][koja], {c, koja}});
}
/// bojim ostale
nd = dst + sve;
if(dist[c][0] > nd){
q.erase({dist[c][0], {c, 0}});
dist[c][0] = nd;
q.insert({dist[c][0], {c, 0}});
}
}
}
ll mn = INF;
for(auto x : dist[n]) mn = min(mn, x.second);
if(mn == INF) cout << "-1\n";
else cout << mn << "\n";
return 0;
}
