#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 203, mod = 1e9 + 7, inf = 1e18 + 7;
struct node
{
int to, col;
ll cost;
};
struct uz
{
ll cost;
int to, col;
friend bool operator<(const uz& a, const uz& b){
if(a.cost == b.cost){
if(a.to == b.to){
return a.col < b.col;
}
return a.to < b.to;
}
return a.cost < b.cost;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("fortmoo.in", "r", stdin);
// freopen("fortmoo.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<map<int, vector<node>>> g(n);
vector<map<int, ll>> sum(n), dp2(n);
vector<ll> dp(n, inf);
for(int i = 0; i < m; ++i){
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
--a, --b;
g[a][c].push_back({b, c, p});
g[b][c].push_back({a, c, p});
sum[a][c] += p;
sum[b][c] += p;
}
set<uz> s;
s.insert({0, 0, 0});
dp[0] = 0;
while(!s.empty()){
auto v = *s.begin();
s.erase(s.begin());
// cout << v.to << "\n";
if(v.col){
for(auto j : g[v.to][v.col]){
ll cost = v.cost + sum[v.to][v.col] - j.cost;
if(cost < dp[j.to]){
s.erase({dp[j.to], j.to, 0});
dp[j.to] = cost;
s.insert({cost, j.to, 0});
}
}
}else{
for(auto i : g[v.to]){
for(auto j : i.second){
ll cost1;
cost1 = v.cost + j.cost;
if(cost1 < dp[j.to]){
s.erase({dp[j.to], j.to, 0});
dp[j.to] = cost1;
s.insert({cost1, j.to, 0});
}
ll cost2;
cost2 = v.cost + sum[v.to][j.col] - j.cost;
if(cost2 < dp[j.to]){
s.erase({dp[j.to], j.to, 0});
dp[j.to] = cost2;
s.insert({cost2, j.to, 0});
}
ll cost3 = v.cost;
if(!dp2[j.to].count(j.col)){
s.erase({dp2[j.to][j.col], j.to, j.col});
dp2[j.to][j.col] = cost3;
s.insert({cost3, j.to, j.col});
}
else if(cost3 < dp2[j.to][j.col]){
s.erase({dp2[j.to][j.col], j.to, j.col});
dp2[j.to][j.col] = cost3;
s.insert({cost3, j.to, j.col});
}
}
}
}
}
if(dp[n - 1] == inf){
cout << -1;
}else{
cout << dp[n - 1];
}
}
