/// - dwuy -
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;
struct Edge{
int u, v, c, col;
Edge(int u=0, int v=0, int col=0, int c=0){
this->u = u;
this->v = v;
this->col = col;
this->c = c;
}
int other(int x){
return u ^ v ^ x;
}
};
int n, m;
Edge edges[MX];
vector<int> G[MX];
map<int, vector<int>> T[MX];
void nhap(){
cin >> n >> m;
for(int i=1; i<=m; i++){
int u, v, col, c;
cin >> u >> v >> col >> c;
edges[i] = Edge(u, v, col, c);
G[u].push_back(i);
G[v].push_back(i);
T[u][col].push_back(i);
T[v][col].push_back(i);
}
}
int d[MX];
map<int, int> sum[MX];
map<int, int> f[MX];
void solve(){
for(int i=1; i<=m; i++){
int u = edges[i].u;
int v = edges[i].v;
int c = edges[i].c;
int col = edges[i].col;
sum[u][col] += c;
sum[v][col] += c;
}
priority_queue<tpiii, vector<tpiii>, greater<tpiii>> Q;
memset(d, 0x3f, sizeof d);
d[1] = 0;
Q.push({0, -1, 1});
while(Q.size()){
int du, cl, u;
tie(du, cl, u) = Q.top();
Q.pop();
if(cl == -1 && d[u] != du) continue;
if(cl != -1 && f[u][cl] != du) continue;
if(cl == -1){
for(int i: G[u]){
int c = edges[i].c;
int cl = edges[i].col;
int v = edges[i].other(u);
int scl = sum[u][cl];
if(f[v].find(cl) == f[v].end()) f[v][cl] = 1e18;
if(d[v] > min(du + c , du + scl - c)){
d[v] = min(du + c , du + scl - c);
Q.push({d[v], -1, v});
}
if(f[v][cl] > du){
f[v][cl] = du;
Q.push({f[v][cl], cl, v});
}
}
}
else{
for(int i: T[u][cl]){
int c = edges[i].c;
int v = edges[i].other(u);
int scl = sum[u][cl];
if(d[v] > du + scl - c){
d[v] = du + scl - c;
Q.push({d[v], -1, v});
}
}
}
}
cout << (d[n] == d[0]? -1 : d[n]);
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
