#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];
map <int, 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][c].push_back({b, i});
graf[b][c].push_back({a, i});
dist[b][c] = INF;
dist[a][c] = 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;
ll dst = q.begin()->first;
q.erase(q.begin());
int v = prr.first;
int vcol = prr.second;
if(vcol == 0){
for(auto &colors : graf[v]){
for(auto pr : colors.second){
int c = pr.first;
int koja = pr.second;
ll p = edg[koja];
int col = clr[koja];
ll sve = cost[v][col] - p;
ll nd;
/// 1 - nije bitno da li menjam granu
nd = dst + min(sve, p);
if(dist[c][0] > nd){
q.erase({dist[c][0], {c, 0}});
dist[c][0] = nd;
q.insert({nd, {c, 0}});
}
/// 2 - menjam granu (i sve iste boje kod c), bitna je
nd = dst;
if(dist[c][col] > nd){
q.erase({dist[c][col], {c, col}});
dist[c][col] = nd;
q.insert({nd, {c, col}});
}
}
}
}
else{
for(auto pr : graf[v][vcol]){
int c = pr.first;
int koja = pr.second;
int p = edg[koja];
ll nd = dst + cost[v][vcol] - p;
if(dist[c][0] > nd){
q.erase({dist[c][0], {c, 0}});
dist[c][0] = nd;
q.insert({nd, {c, 0}});
}
}
}
}
ll mn = dist[n][0];
if(mn == INF) cout << "-1\n";
else cout << mn << "\n";
return 0;
}
