#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using aa = array<int,3>;
using ii = pair<int,int>;
const int N = 1e5+5;
int n, m, u, v, c, kc, p, dp[N];
map<int,int> dp2[N],sum[N];
map<int,vector<aa>> adj[N];
priority_queue<aa,vector<aa>,greater<aa>> pq;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> u >> v >> c >> p;
adj[u][c].push_back({v,p,c});
adj[u][0].push_back({v,p,c});
adj[v][c].push_back({u,p,c});
adj[v][0].push_back({u,p,c});
sum[u][c] += p;
sum[v][c] += p;
dp2[u][c] = dp2[v][c] = 1e18;
}
for (int i = 1; i <= n; i++) dp[i] = 1e18;
dp[1] = 0;
pq.push({0,1,0});
while (!pq.empty()){
aa it = pq.top();
pq.pop();
kc = it[0];
u = it[1];
c = it[2];
if (!c){
if (kc > dp[u]) continue;
for (aa it : adj[u][0]){
int mx = min(it[1],sum[u][it[2]] - it[1]);
// min đổi edge và đổi neighbors
if (dp[it[0]] > dp[u] + mx){
dp[it[0]] = dp[u] + mx;
pq.push({dp[it[0]],it[0],0});
}
/*
giả sử có 1 đường đi: x --(t1)--> y --(t2)--> z
với t1,t2 lần lượt là cost để đổi màu (x,y) và (y,z)
nếu (x,y) và (y,z) cùng màu
=> phải đổi màu 1 trong 2 đường
nếu t1 tối ưu hơn thì dijkstra bình thường
còn nếu t2 tối ưu hơn thì sẽ dùng dp2
=> dp2 đơn giản là skip 1 cạnh và tới cạnh tiếp theo
thay vì dijkstra tuần tự
*/
if (dp2[it[0]][it[2]] > dp[u]){
dp2[it[0]][it[2]] = dp[u];
pq.push({dp[u],it[0],it[2]});
}
}
} else{
// sau khi đã skip 1 cạnh thì phải dijkstra tiếp nếu ko thì WA
if (kc > dp2[u][c]) continue;
for (aa it : adj[u][c]){
// phải đổi màu đường đi
int mx = kc + it[1];
if (dp[it[0]] > mx){
dp[it[0]] = mx;
pq.push({mx,it[0],0});
}
}
}
}
cout << (dp[n] == (int)1e18 ? -1 : dp[n]);
return 0;
}
